[알고리즘] 합병정렬 Merge Sort

합병정렬이란?

두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병
ⓛ 배열 A의 첫번째 값과 B의 첫번째 값을 비교
② 비교한 값  중 작은 값을 반환할 배열C에 입력
③ 배열 C에 넣은 값 다음 값과, 나머지 값을 비교 > 1,2를 반복

사용법

ⓛ 입력된 배열을 나누기
② 나눠진 배열을 정렬
③ 배열을 합치기 (합병정렬 사용)

 

수행시간

O(nlogn)

 

public class MergeSort {
	
	static int[] arr;
	static int[] tmp;
	public void mergeSort(int start, int end) {
		
		if(start<end) {
			int mid = (start+end)/2;
			mergeSort(start, mid);
			mergeSort(mid+1, end);
			merge(start, mid, end);
		}
		
	}
	private void merge(int start, int mid, int end) {
		
		int a = start;
		int b = mid+1;
		int idx = start;
		
		System.out.println("start : "+start+" end : "+end+" mid : "+mid);
		
        //값을 비교해서 담기
		while(a <= mid && b <= end) {		
			if(arr[a]<=arr[b]) {
				tmp[idx++]=arr[a++];
			}
			else{
				tmp[idx++]=arr[b++];
			}
		}
		
        //어느 한쪽이 먼저 끝난 경우, 남은 쪽을 담아주는 로직
		if(a>mid) {
			while(b<=end) {
				tmp[idx++] = arr[b++]; 
			}
		}else {
			while(a<=mid) {
				tmp[idx++] = arr[a++]; 
			}
		}
		
		
		
		for(int i = start; i<=end; i++) {
			arr[i] = tmp[i];
		}
	}
	
	public static void main(String[] args) {
		arr = new int[] {5, 2, 4, 1, 6, 3};
		tmp = new int[arr.length];
		MergeSort f = new MergeSort();
		f.mergeSort(0, arr.length-1);
		System.out.println(Arrays.toString(arr));
		
	}

}