합병 정렬

톱 다운 구현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

1 /// merge sort range : [low ~ high] 2 void mergeSort(int A[], int low, int high, int B[]){ 3     // 1. base condition 4     if(low >= high) return; 5  6     // 2. divide 7     int mid = (low + high) / 2; 8  9     // 3. conquer10     mergeSort(A, low, mid, B);11     mergeSort(A, mid+1, high, B);12 13     // 4. combine14     int i=low, j=mid+1, k=low;15     for(;k<=high;++k){16         if(j > high ) B[k] = A[i++];17         else if(i > mid) B[k] = A[j++];18         else if(A[i] < A[j]) B[k] = A[i++];19         else B[k] = A[j++];20     }21 22     // 5. copy23     for(i=low;i<=high;++i) A[i] = B[i];24 }

바텀 업 구현

// array A[] has the items to sort; array B[] is a work arrayvoid 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];}