[정렬] 병합 정렬 (Merge Sort)

 

평균 및 최악의 시간 복잡도 : O(nlogn)

공간 복잡도 : 상황에 따라 다름

 

분할 정복 방식으로 구현

주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬한다.

그 후 정렬된 배열을 하나로 합쳐서 정렬된 전체 수열을 얻는다.

 

/*
	코드 출처 : 코딩 인터뷰 완전 분석, 인사이트, 게일 라크만 맥도웰
*/

void mergesort(int[] array) {
    int[] helper = new int[array.length];
    mergesort(array, helper, 0, array.length - 1);
}

void mergesort(int[] array, int[] helper, int low, int high) {
    if(low < high) {
    	int middle = (low + high) / 2;
        mergesort(array, helper, low, middle); 		//왼쪽 절반 정렬
        mergesort(array, helper, middle + 1, high); //오른쪽 절반 정렬
        merge(array, helper, low, middle, high);	//병합
    }
}

void merge(int[] array, int[] helper, int low, int middle, int high) {
    for(int i=low; i<=high; ++i) {
    	helper[i] = array[i];
    }
    
    int helperLeft = low;
    int helperRight = middle + 1;
    int current = low;
    
    //왼쪽 절반과 오른쪽 절반을 비교하여 작은 원소를 원래 배열에 복사해 넣는다.
    while(helperLeft <= middle && helperRight <= high) {
    	if(helper[helperLeft] <= helper[helperRight]) {
        	array[current] = helper[helperLeft];
            ++helperLeft;
        } else {
        	array[current] = helper[helperRight];
            helperRight++;
        }
        ++Current;
    }
    
    //왼쪽 절반 배열에 남은 원소들을 원래 배열에 복사해 넣는다.
    int remaining = middle - helperLeft;
    for(int i=0; i<=remaining; ++i) {
    	array[current + i] = helper[helperLeft + i];
    }
}