[Algorithm] Merge Sort (합병 정렬)

폰 노이만이 1945년 개발한 Merge Sort (합병 정렬)은 Divide and Conquer (분할 정복) 알고리즘의 하나입니다.

 

합병 정렬은 순서없이 뒤섞여 있는 배열(Array)을 길이가 1 이하가 될 때까지 분할하고 재귀적으로 정렬하고 다음 정렬된 부분을 병합하는 방법으로 진행합니다.

 

27, 10, 12, 20, 25, 13, 15, 22로 구성된 배열을 nondecreasing order(오름차순)로 정렬하는 Merge Sort는 다음과 같습니다.

 

각각 절반씩 Divide한 후에 길이가 1이하가 되면 정복(Conquer)을 통해 재귀적으로 정렬하고, Merge를 합니다. 최종적으로 Merge된 배열은 nondecreasing order로 정렬되어 있습니다.

 

위의 내용을 토대로 Input이 n, array s[1...n]이고 Output이 nondecreasing order로 정렬된 S[1...n]이 되는 Merge Sort 알고리즘을 다음과 같이 구성해볼 수 있을 것입니다.

 

void mergesort (int n, keytype S[]) {
	const int h = [n / 2], m = n - h;
	keytype U[1..h], V[1..m];
	
    if (n > 1) {
		copy S[1] through S[h] to U[1] through U[h];
		copy S[h+1] through S[n] to V[1] through V[m];
		mergesort(h,U);
		mergesort(m,V);
		merge(h,m,U,V,S);
	}
}