병합 정렬 (Merge Sort)

병합 정렬 (Merge Sort)

작성자 : 김문규
최초 작성일 : 2008.10.16

Pseudo Code

MERGE-SORT A[1 . . n]  (recursive version)
    1.If n= 1, done.
    2.Recursively sort A[1 . . n/2]and A[n/2+1 . . n].
    3.“Merge” the 2 sorted lists.

잘 이해가 되지 않지요? ^^ 설명하지면...
이는 Divide And Conquer의 전형적인 예 입니다.
즉, n개에 대한 처리를 n/2 씩 나누어서 부분을 해결하고 그 결과를 다시 합쳐서 전체를 해결하자는 겁니다.
여기서, 하나 중요한 것은 n/2를 계속 나누어서 1이 될때 까지 쪼개서 처리한다는 것이지요.
결과적으로는 2개씩 비교한 데이터를 모아모아서 n개를 비교하겠다는 것입니다.

20 13 7 2 12 9 1 11
20 13 7 2 | 12 9 1 11         ==> 계속 쪼갠다.
20 13 | 7 2 | 12 9 | 1 11    ==> 2개씩 될 때까지
13 20 | 2 7 | 9 12 | 1 11    ==> 2개씩 비교한다. 정렬한다.
2 7 13 20 | 1 9 11 12         ==> 2개의 그룹(2개의 숫자)을 비교해서 다시 정리한다.
여기서 중요한 사실은 맨 앞에 값을 차례로 비교하면 된다는 사실입니다. 따라서, O(n)의 복잡도를 가지게 됩니다. (하단의 그림을 한번 참고합니다.)
1 2 7 9 11 12 13 20           ==> 다시 2개의 그룹(4개의 숫자)을 비교해서 다시 정리한다.

그림으로 다시 한번 볼까요?

위의 설명은 재귀적 호출(Recursive Call)을 이용하여 구현한 예시 입니다. 이는 Procedure Merge 방식으로 다시 표현도 가능합니다. 이것에 대한 추가적인 내용은 아래의 문서에서 다루겠습니다. 참조하세요.

DivideandConquer(MergeSort).ppt