합병 정렬

합병 정렬 또는 병합 정렬(영어: merge sort 머지 소트^[*])은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다.^[1] 상향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다.^[2]

합병 정렬

합병 정렬의 예
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	O(n log n)
최선 시간복잡도	O(n log n)
평균 시간복잡도	일반적으로, O(n log n)
공간복잡도	О(n)

알고리즘

n-way 합병 정렬의 개념은 다음과 같다.

1. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것과 같으므로)
2. 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.

흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
2. 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
5. 복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

소스 코드

톱 다운 구현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 < 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 < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || A[i] <= 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 < 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 >= 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<=high;++k){
        if(j > high ) B[k] = A[i++];
        else if(i > mid) B[k] = A[j++];
        else if(A[i] <= A[j]) B[k] = A[i++];
        else B[k] = A[j++];
    }

    // 5. copy
    for(i=low;i<=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 < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (i = 0; i < 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 >= 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 < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iRight && (j >= iEnd || A[i] <= 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 < n; i++)
        A[i] = B[i];
}

외부 병합 정렬

외부 병합 정렬(external merge sort)은 대상 데이터가 테이프나 디스크에 저장되어있고 데이터가 너무 커서 메모리에 담을 수 없는 경우에 실용적인 방법이다. 예를 들어, 900MB의 데이터를 100MB의 RAM을 사용하여 정렬을 해야 한다고 해보자.

1. 100MB 데이터를 주메모리에 읽어들이고, quicksort와 같이 일반적인 알고리즘을 사용하여 정렬한다.
2. 정렬된 데이터를 디스크에 쓴다.
3. 1,2 번 과정을 9번 반복한다. 그러면 100MB짜리 파일이 9개 생긴다.
4. 9개의 파일에서 각각 처음부터 10MB 씩을 메모리(입력버퍼)에 로딩한다. 10MB의 출력을 위한 버퍼도 만들어둔다.
5. 9way merge를 수행하고 결과를 출력버퍼에 쓴다. 출력버퍼가 차면 파일에 쓰고, 출력 버퍼를 비운다. 9개의 입력 버퍼가 비워지면, 다음 10MB를 읽는다.