[Algorithm] Merge Sort (병합 정렬)

Merge sort의 특징은 다음과 같다.

• 외부 정렬 방법이다.
• 분할 정복을 이용한다.

Pseudo Code

MERGE

결합 단계에서 정렬된 두 부분 수열을 병합하는 프로시저이다.

MERGE(A, p, q, r)

    n1 = q - p + 1
    n2 = r - q

    create L[1, ..., n1 + 1], R[1, ..., n2 + 1]

    for i = 1 to n1
        L[i] = A[p + i - 1]

    for j = 1 to n2
        R[j] = A[q + j]

    L[n1 + 1] = INF
    R[n2 + 1] = INF

    i = 1
    j = 1

    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

MERGE-SORT

MERGE-SORT(A, p, r)

    if p < r
        q = floor((p + r)/2)
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

수행 시간 분석

n개의 수를 정렬하는 merge sort에서 수행시간 $T(n)$을 다음과 같이 추론할 수 있다.

 

원소의 개수가 1개일 때, merge sort는 상수 시간이 걸린다.

 

또한, 원소의 개수 n이 $n\gt1$일 때에는 수행시간을 다음과 같이 나눌 수 있다.

1. 분할(MERGE-SORT 함수에서 q = floor((p + r)/2) 부분을 의미)
2. 이는 상수 시간이 걸리므로, $\theta(1)$의 시간이 걸린다.
3. 분할 단계에서는 부분 배열의 중간 위치를 계산한다.
4. 정복
5. 두 개의 부분 문제를 재귀적으로 풀어 나가는데, 각 부분 문제의 크기가 $n/2$이므로 $2T(n/2)$의 수행시간이 걸린다.
6. 결합
7. n개의 원소에 대해 MERGE 프로시저는 $\theta(n)$의 시간이 걸린다.

따라서, merge sort의 수행시간 $T(n)$에 대한 점화식은 다음과 같다.

 

$$
T(n)=
\begin{cases}
\theta(1), & \text{if}\ n=1 \
2T(n/2)+cn, & \text{if}\ n\gt1
\end{cases}
$$

 

위 점화식을 마스터 정리 경우 2를 이용하여 풀면, $T(n)=\theta(n\log{n})$이므로, n개의 수를 정렬하는 merge sort의 수행 시간은 $\theta(n\log{n})$이다.

 

마스터 정리에 대해서는 여기를 참고할 것.

 

T. Cormen, C. Leiserson, R. Rivest and C. Stein, 『Introduction to Algorithms』, 문병로, 심규석, 이충세 옮김, 한빛아카데미(2014), p29-p39