병합 정렬(Merge Sort)

간단한 설명

병합 정렬은 존 폰 노이만에 의해 고안된 알고리즘이다.

병합 정렬은 분할정복 기법을 이용하며 다음과 같이 작동한다.

 

분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다.

정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.

결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다.

 

계속해서 분할을 하다 보면 원소의 수가 하나가 되고 이는 원소가 하나임으로 이미 정렬된 수열이다.

이 하나의 원소로 이루어진 부분수열로 부터 각 부분수열을 병합해가면서 정렬하는 알고리즘이 바로 병합 정렬이다.

알고리즘의 설계

알고리즘의 설계를 위해 트리를 하나 생각해보자.

이 트리의 각 정점에는 두 개의 자식노드가 있고(물론 한개의 자식만 가질수도 있다.) 맨 아래쪽의 자식노드에는 원소의 수가 하나인 부분수열이 존재하며, 이들의 부모 노드는 자식 노드의 부분수열을 병합하여 정렬한 부분수열이다. 그러면 맨 위쪽의 노드는 완전히 정렬된 수열이다. 이 트리를 머지 소트 트리라고 한다.

 

맨 아래쪽 노드의 부모노드를 채우는것으로 병합 정렬을 시작하며

부모노드는 각 자식노드의 정점을 맨 앞의 원소부터 차례대로 비교하여 작은 것을 앞에 배치하는 것으로 병합한다.

이때 부모노드에서 완성된 부분수열의 원소의 수가 k일때 병합의 점근적 시간복잡도는 O(k)이다.

 

항상 모든 부분수열을 병합하는데에 걸리는 시간은 부분수열의 원소의 개수의 합이 전체 수열의 원소의 개수이기 때문에 전체 수열의 원소의 수가 N이라면 트리의 층마다 병합하는데 걸리는 전체적인 점근적 시간복잡도는 O(N)이다.

 

또한, 노드가 두 개인 트리를 설정했기 때문에 트리의 층은 log(N)이 된다.(log 는 밑이 2인 로그)

따라서 알고리즘의 전체 시간복잡도는 O(N log(N))이 된다.

 

그리고 병합 정렬을 시행할 때 구지 머지 소트 트리를 만들지는 않아도 된다.

 

글로는 잘 설명이 되지 않을 수 있기 때문에 이해에 도움을 줄 수 있는 gif를 첨부하겠다.

[gif 1] 병합 정렬, wikipedia 병합 정렬

병합 정렬에 대한 이해를 완료했다면 삽입 정렬에 관한 포스팅에 있었던 문제를 병합 정렬로 해결해 보기를 바란다.

 

아래는 예시코드이다.

#include <cstdio>
int A[1003],M[1003],N;
void Merge(int s1,int e1,int s2,int e2){
    int p=s1,q=s2;
    if(e1>N)e1=N;
    if(e2>N)e2=N;
    for(int i=s1;i<=e2;i++){
        if((A[p]<A[q]&&p<=e1)||q>e2){
            M[i]=A[p];
            p++;
        }else{
            M[i]=A[q];
            q++;
        }
    }
    for(int i=s1;i<=e2;i++){
        A[i]=M[i];
    }
}
void Sort(int s,int e){
    if(s<e){
        Sort(s,(s+e)/2);
        Sort((s+e)/2+1,e);
    }
    Merge(s,(s+e)/2,(s+e)/2+1,e);
}
int main(){
    int i,st=1;
    scanf("%d",&N);
    while(N>st)st*=2;
    for(i=1;i<=N;i++)scanf("%d",&A[i]);
    Sort(1,st);
    for(i=1;i<=N;i++)printf("%d ",A[i]);
    return 0;
}

Reference

wikipedia 합병 정렬

INTRODUCTION TO ALGORITHMS THIRD EDITION (Thomas H. Cormen, Charles E. Lesierson, Ronald L. Rivest, Clifford Stein)