Merge Sort: 합병 정렬

* Merge Sort?

 

합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 방식이다. 합병 정렬은 분할 정복(divide and conquer) 기반이라고 볼 수 있다. 

합병 정렬은 다음의 단계들로 이루어진다.

1. 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 
2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 
3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다. 

보라색 부분은 분할, 초록색 부분은 정복하는 과정이라고 할 수 있겠다.

 

* Pseudocode

 

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다. 합병 정렬은 추가적인 리스트를 필요로 한다. 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두개의 리스트의 요소 중에 더 작은 요소를 새로운 리스트로 옮긴다. 둘 중에서 하나가 끝날 때 까지 이 과정을 반복한다. 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사하면 된다. 

* 분석

합병 정렬은 순환 호출 구조로 되어 있다. 따라서 레코드의 개수 n이 2의 거듭제곱이라 가정해보자. n이 2^3인 경우에는 부분 배열의 크기가 2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 따라서 일반적으로 n = 2^k라고 하면 부분 배열의 크기는 2 ^ k -> 2 ^ (k-1) -> ... -> 2 ^ 0이 되어 순환 호출의 깊이가 k가 될 것이고, k는 log2n임이 될 것이다. 부분 배열이 합쳐지는 합병 단계(merge)에서 비교 연산과 이동 연산이 수행된다. 이러한 합병 단계는 순환호출의 깊이(k)만큼 반복적으로 일어난다. 그렇다면 각 합병 단계에서 비교 연산은 몇번 수행될까?

n = 2^3일 때, 크기가 1인 부분 배열 2개를 합병하는데에는 최대 2개의 비교연산이 필요하고, 부분 배열의 쌍이 4개이므로 2*4 =8번의 비교 연산이 필요하다. 다음 단계에서는 크기가 2인 부분배열을 합치는데 최대 4번의 비교 연산이 필요하며, 부분배열 쌍이 2개 있으므로 역시 4*2=8번의 연산이 필요함을 알 수 있다. 마지막 합병 단계인 크기가 4인 부분 배열 2개를 합병하는 데에는 최대 8번의 비교 연산이 필요하다. 따라서 8*1번의 연산이 필요함을 알 수 있다. 따라서 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요하기 때문에 합병 단계는 log2n만큼 있으므로 총 비교연산은 nlog2n번 필요하다. 그렇다면 이동 연산은 몇 번 수행될까?

하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 하므로 이동 연산은 총 부분 배열에 들어 있는 요소 의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서 log2n개의 합병 단계가 필요하므로 이동 단계는 2nlog2n개의 이동 연산이 필요한 것이다. 어쨋든 합병 정렬은 비교연산은 nlog2n, 이동 연산은 2nlog2n이므로 시간복잡도는 O(nlog2n)가 된다. 

합병 정렬의 또다른 장점은 데이터의 분포에 영향을 덜 받는다. 즉 최악, 평균, 최선의 경우가 다같이 O(nlog2n)정렬 방법이다.

합병 정렬의 단점은 임시 배열이 필요하다는 것과 만약 레코드의 크기가 큰 경우에는 이동 횟수가 많으므로 합병 정렬은 매우 큰 시간적 낭비를 초래한다. 그러나 레코드를 연결 리스트로 구성하여 합병 정렬하면 링크 인덱스만 변경하면 되므로 데이터의 이동은 크게 신경쓰지 않아도 된다.