병합 정렬(Merge sort)

정렬 알고리즘 중 하나인 병합 정렬(Merge sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다.

---

분할 정복

병합 정렬은 분할 정복(divide-and-conquer)라는 접근법을 이용하는 정렬 알고리즘입니다. 그렇기 때문에 분할 정복이 무엇인지 살펴봐야 합니다. 분할 정복은 문제를 작게 쪼개서 해결하는 방식입니다. 구체적으로는 다음 3단계를 거쳐 문제를 해결합니다.

 

1. 분할(divide) 하나의 커다란 문제를 그보다 크기가 작은 하위 문제(subproblem)로 분할합니다. 하위 문제는 기존 문제와 크기만 다를 뿐, 같은 문제여야 합니다.
2. 정복(conquer) 문제가 충분히 작아질 때까지 계속해서 하위 문제로 분할합니다. 문제가 충분히 작아지게 되면, 문제를 단도직입적으로 풀어버립니다.
3. 병합(combine) 정복 단계에서 해결된 하위 문제들을 병합해서 기존 문제의 해답을 구합니다.

병합 정렬

분할 정복을 병합 정렬에 대입해서 생각하면 다음과 같습니다.

 

1. 분할(divide) n개의 배열을 크기가 n/2인 2개의 배열로 분할합니다.
2. 정복(conquer) 분할된 2개의 배열을 각각 정렬합니다. 
3. 병합(combine) 이제 분할된 2개의 배열 각각은 정렬되어 있습니다. 이들을 병합해 하나의 정렬된 배열을 만듭니다.

여기서 주목할 점은 정복 단계에서 크기가 n인 배열 대신에 크기가 n/2인 배열을 정렬하는 문제를 풀어야 한다는 점입니다. 크기가 작아졌긴 하지만, n/2는 여전히 큰 수일 수 있습니다. 이 경우 다시 문제를 분할합니다.

 

의사 코드는 아래와 같습니다. 

 

위 함수는 배열 A를 인덱스 p 부터 r 까지 정렬하는 함수입니다.

 

우선 배열을 반으로 분할하기 위해 배열의 중간 인덱스를 구합니다(line 2). 그리고 배열을 절반으로 나누어, 각각 정렬합니다(line 3-4). 배열의 절반을 정렬할 때는 또 다시 병합 정렬을 사용하면 됩니다. 그러면 원소가 하나가 될 때까지 분할이 계속될 것입니다. 원소가 하나인 배열은 이미 정렬된 것이나 다름 없으므로, 그 다음에는 병합 단계로 넘어갑니다. 

예시

[5, 2, 4, 7, 1, 3, 2, 6]을 정렬하는 것으로 예시해보겠습니다.

 

1. 분할(divide) 우선 이 배열을 [5, 2, 4, 7]과 [1, 3, 2, 6]으로 분할합니다.
2. 정복(conquer) 분할된 두 배열을 정렬해 [2, 4, 5, 7]과 [1, 2, 3, 6]으로 만듭니다.
3. 병합(conbine) 하나의 정렬된 배열 [1, 2, 2, 3, 4, 5, 6, 7]로 병합합니다.

 

문제는 [5, 2, 4, 7]과 [1, 3, 2, 6]로 정렬하는 방법입니다. 이는 또 다시 병합 정렬을 재귀적으로 사용해가면서 구하면 됩니다.

 

1. 분할(divide) [5, 2, 4, 7]을 [5, 2]와 [4, 7]로 나눕니다.
2. 정복(conquer) 분할된 두 배열을 정렬해 [2, 5]와 [4, 7]로 만듭니다.
3. 병합(conbine) 하나의 정렬된 배열 [2, 4, 5, 7]로 병합합니다.

 

그림으로 그려보면 아래와 같습니다. 배열을 개별 원소가 될 때까지 분할한 후, 병합하는 단계에서 크기에 맞게 병합하는 방식입니다. 여기서 보듯이 병합 정렬에서 중요한 건 병합 단계임을 알 수 있습니다.

 

병합하는 방법

병합 정렬의 핵심은 병합 단계에 있습니다. 병합 단계는 카드를 정렬하는 것에 비유해보겠습니다. 두 개의 카드 더미가 있다고 놓여있습니다. 두 카드 더미는 작은 수가 위로 오도록 이미 정렬되어 있는 상태입니다. 두 카드 더미에서 제일 위에 있는 카드 두 장을 비교합니다. 그중 작은 수를 손으로 가져옵니다. 다시 제일 위에 있는 카드 두 장을 비교합니다. 그중 작은 수를 손으로 가져옵니다... 이렇게 반복하다보면, 두 카드 더미를 모두 정렬된 상태로 손으로 가져올 수 있습니다. 

코드

병합 단계를 의사 코드로 표현하면 아래와 같습니다.

우선 배열 $A$를 $L$과 $R$로 분할합니다. 그리고 $L$과 $R$의 원소들을 작은 것부터 차례대로 비교하기 시작합니다. 이때 $L$과 $R$의 마지막 원소에 $∞$을 추가하는데, 그 이유는 $L$이나 $R$ 중 어느 한 곳의 카드 더미가 먼저 바닥나는 경우에 대비한 것입니다.

 

파이썬으로는 아래와 같이 작성할 수 있습니다. 배열 $A$ 전체를 정렬하려고 싶으면 merge_sort(A, 0, len(A))라고 입력하면 됩니다.

def merge(A, p, q, r):
    L = A[p:q]
    R = A[q:r]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    for k in range(p, r):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, p, r):
    if p < r-1:
        q = (p+r)//2
        merge_sort(A, p, q)
        merge_sort(A, q, r)
        merge(A, p, q, r)

복잡도

병합 정렬의 복잡도를 분석해보겠습니다. 우선 병합 단계의 시간 복잡도는 $\Theta(n)$입니다. 그러므로 트리 모양의 뿌리 부분(마지막에 이뤄지는 병합)에서 $\Theta(n)$이 소요됩니다. 그 아래 부분 하위 문제를 풀 때는 $\Theta(n/2)$만큼 소요됩니다. 그 대신 문제가 2개가 되므로 x2를 해줘야 합니다. 그 아래에서는 $\Theta(n/4)$x4가 소요됩니다. 즉 모든 층에서 $\Theta(n)$만큼의 비용이 듭니다. 이 같은 방식으로 계산해보면, $\Theta(n)$에 트리의 높이를 곱해준 만큼 시간이 소요됩니다. n개의 원소로 이루어진 트리의 높이는 log$_2n$이므로, 병합 정렬의 복잡도는 $\Theta(n$log$_2n)$임을 알 수 있습니다.