합병 정렬

합병 정렬 또는 병합 정렬(merge sort)은 "O"("n" log "n") 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 상향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다.
알고리즘.
n-way 합병 정렬의 개념은 다음과 같다.
흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.
소스 코드.
톱 다운 구현1.
// Array A[] has the items to sort; array B[] is a work array.
TopDownMergeSort(A[], B[], n)
 CopyArray(A, 0, n, B); // duplicate array A[] into B[]
 TopDownSplitMerge(B, 0, n, A); // sort data from B[] into A[]
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
TopDownSplitMerge(B[], iBegin, iEnd, A[])
 if(iEnd - iBegin &lt; 2) // if run size == 1
 return; // consider it sorted
 // split the run longer than 1 item into halves
 iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
 // recursively sort both runs from array A[] into B[]
 TopDownSplitMerge(A, iBegin, iMiddle, B); // sort the left run
 TopDownSplitMerge(A, iMiddle, iEnd, B); // sort the right run
 // merge the resulting runs from array B[] into A[]
 TopDownMerge(B, iBegin, iMiddle, iEnd, A);
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
TopDownMerge(A[], iBegin, iMiddle, iEnd, B[])
 i = iBegin, j = iMiddle;
 // While there are elements in the left or right runs...
 for (k = iBegin; k &lt; iEnd; k++) {
 // If left run head exists and is &lt;= existing right run head.
 if (i &lt; iMiddle &amp;&amp; (j &gt;= iEnd || A[i] &lt;= A[j])) {
 B[k] = A[i];
 i = i + 1;
 } else {
 B[k] = A[j];
 j = j + 1;
CopyArray(A[], iBegin, iEnd, B[])
 for(k = iBegin; k &lt; iEnd; k++)
 B[k] = A[k];
톱 다운 구현2.
/// merge sort range : [low ~ high]
void mergeSort(int A[], int low, int high, int B[]){
 // 1. base condition
 if(low &gt;= high) return;
 // 2. divide
 int mid = (low + high) / 2;
 // 3. conquer
 mergeSort(A, low, mid, B);
 mergeSort(A, mid+1, high, B);
 // 4. combine
 int i=low, j=mid+1, k=low;
 for(;k&lt;=high;++k){
 if(j &gt; high ) B[k] = A[i++];
 else if(i &gt; mid) B[k] = A[j++];
 else if(A[i] &lt;= A[j]) B[k] = A[i++];
 else B[k] = A[j++];
 // 5. copy
 for(i=low;i&lt;=high;++i) A[i] = B[i];
바텀 업 구현.
// array A[] has the items to sort; array B[] is a work array
void BottomUpMergeSort(A[], B[], n)
 // Each 1-element run in A is already "sorted".
 // Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted.
 for (width = 1; width &lt; n; width = 2 * width)
 // Array A is full of runs of length width.
 for (i = 0; i &lt; n; i = i + 2 * width)
 // Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
 // or copy A[i:n-1] to B[] ( if(i+width &gt;= n) )
 BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
 // Now work array B is full of runs of length 2*width.
 // Copy array B to array A for next iteration.
 // A more efficient implementation would swap the roles of A and B.
 CopyArray(B, A, n);
 // Now array A is full of runs of length 2*width.
// Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1 ].
void BottomUpMerge(A[], iLeft, iRight, iEnd, B[])
 i = iLeft, j = iRight;
 // While there are elements in the left or right runs...
 for (k = iLeft; k &lt; iEnd; k++) {
 // If left run head exists and is &lt;= existing right run head.
 if (i &lt; iRight &amp;&amp; (j &gt;= iEnd || A[i] &lt;= A[j])) {
 B[k] = A[i];
 i = i + 1;
 } else {
 B[k] = A[j];
 j = j + 1;
void CopyArray(B[], A[], n)
 for(i = 0; i &lt; n; i++)
 A[i] = B[i];
외부 병합 정렬.
외부 병합 정렬(external merge sort)은 대상 데이터가 테이프나 디스크에 저장되어있고 데이터가 너무 커서 메모리에 담을 수 없는 경우에 실용적인 방법이다.
예를 들어, 900MB의 데이터를 200MB의 RAM을 사용하여 정렬을 해야 한다고 해보자.