Merge Sort(합병정렬)

1. 합병정렬

• 비교기반 정렬 알고리즘
• 일반적인 방법으로 구현했을때 이 정렬은 안정 정렬에 속함
• 분할 정복 알고리즘의 하나
• 존 폰 노이만이 1945년에 개발
• 복잡도: 최선,평균,최악 모두 nlogn
• n-way 합병 정렬의 개념
  • 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할함(하나의 요소만 있는 리스트는 정렬된 것 같으므로)
  • 부분리스트가 하나만 남을 때까지 반복해서 병합하여 정렬된 부분리스트를 생성.
  • 마지막은 남은 부분리스트가 정렬된 리스트.
• 흔히 쓰이는 하향식 2-way 합병정렬 다음과 같다
  • 리스트의 길이가 1이하이면 이미 정렬된 것
  • 그렇지 않은 경우에는
  • 분할(divide):정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  • 정복(conquer): 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬
  • 결합(combine): 두 부분리스트를 다시 하나의 정렬된 리스트로 합병. 이 때 정렬결과가 임시배열에 저장됨.
  • 복사(copy): 임시배열에 저장된 결과를 원래 배열에 복사.

2. 소스코드

2.1 톱다운 구현(1)

// Array A[] has the items to sort; array B[] is a work array.
function topDownMergeSort(arr1, arr2, n)
{
    copyArray(arr1, 0, n, arr2);           // duplicate array A[] into B[]
    copDownSplitMerge(arr2, 0, n, arr1);   // 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).
function topDownSplitMerge(arr2, iBegin, iEnd, arr1)
{
    if(iEnd - iBegin < 2)                       // if run size == 1
        return;                                 //   consider it sorted
    // split the run longer than 1 item into halves
    let iMiddle = (iEnd + iBegin) / 2;              // iMiddle = mid point
    // recursively sort both runs from array A[] into B[]
    topDownSplitMerge(arr1, iBegin, iMiddle, arr2);  // sort the left  run
    topDownSplitMerge(arr1, iMiddle, iEnd, arr2);  // sort the right run
    // merge the resulting runs from array B[] into A[]
    topDownMerge(arr2, iBegin, iMiddle, iEnd, arr1);
}

//  Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1   ].
// Result is            B[ iBegin:iEnd-1   ].
function topDownMerge(arr1, iBegin, iMiddle, iEnd, arr2)
{
    let i = iBegin; 
    let j = iMiddle;

    // While there are elements in the left or right runs...
    for (let k = iBegin; k < iEnd; k++) {
        // If left run head exists and is <= existing right run head.
        if (i < iMiddle && (j >= iEnd || arr1[i] <= arr1[j])) {
            arr2[k] = arr1[i];
            i = i + 1;
        } else {
            arr2[k] = arr1[j];
            j = j + 1;
        }
    }
}

function CopyArray(arr1[], iBegin, iEnd, arr2[])
{
    for(let k = iBegin; k < iEnd; k++)
        arr2[k] = arr1[k];
}

2.2 톱다운구현(2)

/// merge sort range : [low ~ high]
function mergeSort(arr1, low, high, arr2){
    // 1. base condition
    if(low >= high) return;

    // 2. divide
    let mid = (low + high) / 2;

    // 3. conquer
    mergeSort(arr1, low, mid, arr2);
    mergeSort(arr1, mid+1, high, arr2);

    // 4. combine
    let i = low;
    let j = mid+1;
    let k=low;
    for(;k<=high;++k){
        if(j > high ) {
          arr2[k] = arr1[i++];
        } else if(i > mid) {
          arr2[k] = arr1[j++];
        } else if {
          (arr1[i] <= arr1[j]) arr2[k] = arr1[i++];
        } else { 
          arr2[k] = arr1[j++];
        }
    }

    // 5. copy
    for(;i<=high;++i) {
      arr1[i] = arr2[i];
    }
}

2.3 바텀업 구현

function bottomUpMergeSort(arr1, arr2, 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 (let width = 1; width < n; width = 2 * width)
    {
        // Array A is full of runs of length width.
        for (let 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(arr1, i, Math.min(i+width, n), Math.min(i+2*width, n), arr2);
        }
        // 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  ].
function bottomUpMerge(arr1, iLeft, iRight, iEnd, arr2)
{
    let i = iLeft; 
    let j = iRight;
    // While there are elements in the left or right runs...
    for (let 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])) {
            arr2[k] = arr1[i];
            i = i + 1;
        } else {
            arr2[k] = arr1[j];
            j = j + 1;
        }
    }
}

function copyArray(arr2, arr1, n)
{
    for(let i = 0; i < n; i++)
        arr1[i] = arr2[i];
}

Tip

• 안정 정렬(stable sort)
  • 중복된 값을 입력 순서와 동일하게 정렬한다. 예를 들어 다음 그림과 같이 지역별 발송 시각을 시간 순으로 정렬한 택배 발송 로그가 있다고 가정해보자. 안정 정렬의 경우에는 기존의 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이뤄진다. 그러나 불안정 정렬의 경우에는 시간순으로 정렬한 값을 지역명으로 재정렬하면 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞이고 만다