[정렬] 병합 정렬(Merge Sort)

- 병합 정렬은 먼저 입력을 반으로 나눈다.

- 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다.

- 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다.

- 병합 정렬은 자신에 비해 크기가 반인 문제를 두 개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다.

 

다음은 병합 정렬 알고리즘이다.

mergeSort(A[], p, r){
    if(p<r) then{
        q ← (p+r)/2;
        mergeSort(A, p, q);
        mergeSort(A, q+1, r);
        merge(A, p, q, r);
    }
}

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

 

병합 정렬의 시간 복잡도

따라서,

시간 복잡도는 T(n) = T(n/2) + T(n/2) + n이다.

병합 정렬의 수행 시간은 최악의 경우 O(n log n)이 된다.