10. 합병정렬 (merge sort)

- 분할정복알고리즘(Divide and Conquer)

그냥 말 그대로, 배열을 분할하고, 해결하고, ... 이를 반복하는 알고리즘이다.

 

1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

2. 정복 : 각각의 작은 문제를 순환적으로 해결

3. 합병 : 작은 문제의 해를 합하여(merge), 원래 문제에 대한 해를 구함

 

대표적인 분할정복알고리즘에는 합병정렬(merge sort)과 퀵정렬(quick sort)이 있다.

 

분할은 하나의 큰 문제를 각자 작은 문제로 나누는 것이다. 이 각각의 작은 문제들은 원래 문제와 동일한 문제여야 한다.

정복이라는 의미는 각각의 작은 문제를 해결하는 것이다.

 

 

위의 그림은 합병정렬을 간단하게 표현한 예이다.

예를 들어 위의 배열에서 최댓값을 구하는 문제를 푼다고 가정하자.

순서 :

1. 하나의 큰 문제를 동일한 크기의 작은 문제 두 개로 나누었다. (분할. divide)

2. 각각의 작은 문제 두 개에서 최댓값을 각각 구한다. (정복. conquer)

3. 첫 번째 작은 문제에서의 최댓값과, 두 번째 작은 문제에서의 최댓값을 비교해 최종 위 배열의 최댓값을 구한다. (합병. merge)

 

분할정복법은 기본적으로 순환(recursion)을 이용한다.

 

 

 

 

또 다른 예를 보자.

초기 배열은 52471326이다. 이를 합병정렬해 122345의 정렬된 결과를 만드는 예이다.

 

 

 

합병정렬의 Sudo Code (의사 코드)

mergeSort(A[], p, r)    // A[p... r]을 정렬한다.
{
    if (p < r) then {
        q <- (p + q) / 2;       // (1) p, q의 중간 지점 계산
        mergeSort(A, p, q);    // (2) 전반부 정렬
        mergeSort(A, q+1, r); // (3) 후반부 정렬
        merge(A, p, q, r);      // (4) 합병
    }
}

merge(A[], p, q, r)
{
    정렬되어 있는 두 배열 A[p...q]와 A[q+1... r]을 합하여
    정렬된 하나의 배열 A[p...r]을 만든다.
}

 

 

자바 소스 코드

void merge (int data[], int p, int q, int r)

{

    int i = p, j = q+1, k = p;

    int tmp[data.length()];

    while (i <= q && j <= r) {

        if (data[i] <= data[j])

            tmp[k++] = data[i++];

        else

            tmp[k++] = data[j++];

    }

    while (i <= q)

        tmp[k++] = data[i++];

    while (j <= r)

        tmp[k++] = data[j++];

    for (int i = p; i <= r; i++)

        data[i] = tmp[i];

}

 

시간복잡도

T(n) = 0                         (n=1)

        T(n/2) + T(n/2) + n   (otherwise)