합병 정렬

'''합병 정렬''' 또는 '''병합 정렬'''()은 ''O''(''n'' log ''n'') 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. 존 폰 노이만이 1945년에 개발했다. 상향식 합병 정렬에 대한 자세한 설명과 분석은 1948년 초 헤르만 골드스타인과 폰 노이만의 보고서에 등장하였다.
n-way 합병 정렬의 개념은 다음과 같다.
# 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것과 같으므로)
# 부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 마지막 남은 부분리스트가 정렬된 리스트이다.
흔히 쓰이는 하향식 2-way 합병 정렬은 다음과 같이 작동한다.
# 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
# 분할(divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
# 정복(conquer): 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
# 결합(combine): 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 이때 정렬 결과가 임시배열에 저장된다.
# 복사(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 (AiEnd is not in the set).
TopDownSplitMerge(B, iBegin, iEnd, A)
{
    if(iEnd - iBegin = iEnd 
 Ai 
=== 톱 다운 구현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 ) Bk = Ai++;
        else if(i > mid) Bk = Aj++;
        else if(Ai 
=== 바텀 업 구현 ===
// 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) )
            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 AiLeft :iRight-1.
// Right run is AiRight: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 
 Ai 
외부 병합 정렬(external merge sort)은 대상 데이터가 테이프나 디스크에 저장되어있고 데이터가 너무 커서 메모리에 담을 수 없는 경우에 실용적인 방법이다.
예를 들어, 900MB의 데이터를 100MB의 RAM을 사용하여 정렬을 해야 한다고 해보자.
# 100MB 데이터를 주메모리에 읽어들이고, quicksort와 같이 일반적인 알고리즘을 사용하여 정렬한다.
# 정렬된 데이터를 디스크에 쓴다.
# 1,2 번 과정을 9번 반복한다. 그러면 100MB짜리 파일이 9개 생긴다.
# 9개의 파일에서 각각 처음부터 10MB 씩을 메모리(입력버퍼)에 로딩한다. 10MB의 출력을 위한 버퍼도 만들어둔다.
# 9way merge를 수행하고 결과를 출력버퍼에 쓴다. 출력버퍼가 차면 파일에 쓰고, 출력 버퍼를 비운다. 9개의 입력 버퍼가 비워지면, 다음 10MB를 읽는다.
*
*. Also  Practical In-Place Mergesort. Also 
* 
*
*
* 
* 
* 
*  Animated Sorting Algorithms: Merge Sort - Allows stepping through the steps in the algorithm.
*  Dictionary of Algorithms and Data Structures: Merge sort
*  Mergesort applet with "level-order" recursive calls to help improve algorithm analysis
*  Open Data Structures - Section 11.1.1 - Merge Sort
분류:정렬 알고리즘
분류:비교 정렬
분류:안정 정렬