(6) 합병 정렬법(Merge Sorting)

 일반적으로 합병(merge)이란 각각 정렬된 리스트들을 하나의 정렬된 리스트로 만드는 것이다.
특히 2개의 리스트를 합병하는 것을 2원 합병(two way merge)이라 하며 합병의 예를 그림으로
나타내면 그림 13과 같다.


(그림 13) 이원 합병의 예

 합병 정렬에서는 합병하고자 하는 2개의 리스트가 배열에 존재한다. 두 리스트는 각각 시작 위
치와 끝 위치에 의하여 구별된다. 그림 13의 2개의 리스트는 그림 14와 같이 저장된다.


 (그림 14) 일차원 배열에서의 이원 합병

 그림 14에서 합병하고자 하는 2개의 리스트는 일차원  배열 X에 저장되어 서로 인접하며 위치
를 나타내기 위하여 변수들 f, m, n을 사용한다. 합병된 결과는  같은 크기의 일차원 배열Z에 저
장된다. 이러한 합병 과정을 프로그램으로 작성하면 리스트 12와 같다.

(리스트 12) 이원 합병
void Merge(int x[], int z[], int f[], int m, int n)
{
    int i, j, k, t;

    i=f;           /* 첫 리스트의 시작 위치 */
    j=m+1;        /* 둘째 리스트의 시작 위치 */
    k=f;           /* 합병 결과를 저장할 리스트의 시작 위치 */
    while ((i<=m)&&(j<=n))   /* 두 리스트중 하나가 끝날 때까지 반복 */
    {
        if (x[i]<=x[j])
        {
            z[k]=x[i];          /* 첫 리스트의 키값을 이동 */
            i=i+1;
        }
        else
        {
            z[k]=x[j];         /* 둘째 리스트의 키값을 이동 */
            j=j+1;
        }
        k=k+1;
    }
    if (i>m)
        for (t=j;t<=n;t++)     /* 둘째 리스트에서 남은 키값을 이동 */
            z[k+t-j]=x[t];
    else
        for (t=i;t<=m;t++)    /* 첫 리스트에서 남은 키값을 이동 */
            z[k+t-i]=x[t];
}

 리스트 12의 Merge 알고리즘의 시간을 분석하면 while 루프는 두 리스트 중 어느 하나의 리
스트의 마지막 키값이 Z로 이동했을 때 끝난다. 그리고 두 리스트 중 어느 한 리스트에 남은 키
들이 for문에 의하여 Z로 이동되므로 총 시간은 두 리스트의 키값들의 수에  의하여 결정된다.
따라서 O(n-f+1)의 시간이 소요된다.
 합병 정렬에서는 위에서 설명된 합병 알고리즘을 반복해서 사용한다. 먼저 합병될 리스트의
길이(즉 리스트에 포함된 키들의 수)를 1로 하고 두 리스트를 쌍으로 합병을 수행하여 길이가
2인 n/2개의 리스트를 만든다. 계속하여 길이 2인 두 리스트를 쌍으로 하여 길이 4인 리스트로
합병한다. 이러한 합병 과정은 길이가 n인 하나의 리스트로 합병될 때까지 반복한다. 이러한
 합병 과정은 길이가 n인 하나의 리스트로 합병될 때까지 반복한다. 이러한 과정을 예로 들면
그림 15와 같다.  그림 15에서 합병된 리스트를 쉽게 구별하기 위하여 대괄호([ ])를 사용한다.


(그림 15) 합병 정렬의 예

 그림 15에서 합병할 리스트를 쌍으로 묶을 때 마지막 남은 리스트의 짝이 없을 때는 그 리스트
를 그래로 남겨둔다. 합병 정렬의 알고리즘을 작성하기 전에 그림  15에서와 같이 전체 합병 정
렬은 합병할 리스트의 길이에 따라 몇 단계로 나누어져 있음을 알 수 있다. 한 단계에서 합병할
리스트의 쌍들은 모두 같은 길이이며 인접해 있다. 단 마지막 쌍은 서로 다른 길이 일 수  있다.
따라서 각 단계를 프로그램으로 작성할 때 해당 단계에서 적용되는 길이를 매개 변수로 받아들
여 두 리스트의  시작 위치와 끝 위치를 결정할 수 있다. 예를 들면, 길이 1인 리스트를 합병할때
합병할 쌍들의 위치 변수들 (f, m, n)은 (1, 2, 3), (3, 3, 4), (5, 5, 6)......의 순으로 결정된다.
따라서 합병할 리스트의 길이를 매개 변수  length에 받아들일 때, i=1의 초기값에 대하여 (i, i+
length-1, i+2*length-1)로 결졍되며 매번 i=i+2*length로  증가시킨다. 길이가 2일 때도 이
러한 공식이 적용될 수 있음을  알 수 있다. 따라서 이러한 방법으로 length를 매개 변수로 받아
들여 한 단계를 수행하는 프로그램을 작성하면 리스트 13과 같다.

(리스트 13) 합병 정렬의 한 단계
void Merge_Pass(int x[], int y[], int n, int length)
{
    int i, t;
    i=1;
    while (i<=(n-2*length+1))     /* 길이가 length인 인접한 두 리스트를 계속해서 합병 */
    {
        Merge(x, y, i, i+length-1, i+2*length-1);
        i=i+2*length;
    }
    if ((i+length-1)<n)
        Merge(x, y, i, i+length-1, n);     /* 남은 두 리스트를 합병 */
    else
    {
        for (t=i;t<=n;t++)                /* 남은 하나의 리스트의 키값들은 그대로 이동 */
            y[t]=x[t];
    }
}

 리스트 13의 Merge_Pass는 합병하고자 하는 리스트 X의 키들을 합병한 후, 모두 리스트
Z에 저장하므로 연산 시간은 O(n)이 된다. 이제 각 단계에서 합병할  리스트의 길이를 결정
하여 리스트 13을 반복시키는 부분을 작성하면 합병 정렬이 되고 리스트 14와 같이 작성할
수 있다.

(리스트 14) 합병 정렬
void Merge_Sort(int x[], int n)
{
    int length;
    int y[SIZE];

    length=1;          /* 리스트의 길이를 1로 초기화 */
    while (length<n)   /* 합병된 리스트의 길이가 n이 될 때까지 반복 */
    {
        Merge_Pass(x, y, n, length);    /* x에 저장된 리스트를 y에 합병 */
        length=2*length;                /* 리스트의 길이를 두배로 만든다 */
        Merge_Pass(y, x, n, length);    /* y에 자장된 리스트를 x에 합병 */
        length=2*length;                /* 리스트의 길이를 두배로 만든다 */
    }
}

합병 정렬의 분석

 리스트 14는 리스트의 길이가 매번 2배씩 증가하므로 반복 횟수는  log2n이며 합병한 리스
트의 길이가 n이 되면 정렬이 완료된다. 따라서 리스트 14는 log2n번 리스트  13을 반복 수
행하고 리스트 13은 O(n)번의 시간을 소요하므로 총 소요 시간은 O(nlog2n)이 된다.