[알고리즘] 합병정렬(Merge sort)이란?

1. 합병정렬이란?

Merge sort
합병정렬(Merge sort)이란, 분할과 정복(divide and conquer)의 개념을 이용하여 주어진 배열이 하나의 원소들을 가질 때 까지 쪼개고, 다시 합치는 방식으로 정렬하는것을 말한다. 이미 ‘정렬된 리스트 두 개가 주어지고, 그 두 개를 합쳐서 새로운 정렬된 리스트를 만든다’ 라고 정리할 수 있다.
리스트들을 쪼개서 원소를 하나 가진 리스트가 되면, 그 리스트는 이미 내부적으로는 정렬이 완료된 리스트가 된다. 그렇게 정렬이 완료된 두 개의 리스트의 원소를 비교해서 합치면, 정렬이 완료된 리스트 하나가 탄생하게 되는 원리이다.
 

2. 합병정렬의 예시

array A = {5,2,4,7,1,3,2,6}이 주어졌을 때, 이 배열 A를 merge sort를 이용해 오름차순으로 정렬한다고 생각해보자.

merge sort는 divide and conquer를 이용하므로 일단 먼저 배열을 1개 원소를 가진 어레이가 될 수 있도록 계속 나누어준다. 그러게 되면 우리는 {5}, {2}, {4}, {7}, {1}, {3}, {2}, {6} 이렇게 1개의 원소를 가진 array 8개를 얻게 되고,

이후 각 array들을 비교해서 정렬해나가는 과정을 통해 전체 정렬을 할 수 있게 된다. 앞에서부터 보면, {5}와 {2}를 비교했을 때, 2가 5보다 작으므로 {2,5}로 정렬된 배열을 가지게 된다.
한 단계 merge를 끝내고 나면 {2,5}, {4,7}, {1,3}, {2,6} 총 4개의 어레이를 얻을 수 있다. 다음 단계에서는 각 원소의 첫 번째(해당 배열에서 가장 작은 값)를 비교하게 된다. {2,5}와 {4,7}에서 각 첫 번째 원소는 2와 4이므로 그 둘을 비교하면 2가 가장 작으므로 맨 앞에 오게 된다. 그 다음은 첫번째 배열의 두번째 원소인 5와, 아직 정렬되지 못한 4를 비교해서 더 작은 4를 2 뒤에 배치하게 되고, 이후에는 5와 7을 비교해서 최종적으로 {2,4,5,7}의 배열을 만들게 된다.
두 개를 비교해서 더 작은 값은 정렬의 결과로 내보내고 큰 값은 다음으로 비교할 값을 값을 가져와서 비교한 뒤 정렬하는 방식이라고 생각하면 될 것 같다.

3. 합병정렬의 pseudo code

MERGE-SORT(A,p,r)
	if p<r
    	then q <- ⌊(p+r)/2⌋
        MERGE-SORT(A,p,q)
        MERGE-SORT(A,q+1,r)
        MERGE(A,p,q,r)

merge sort를 하는 경우, 주어져야 할 것은 배열 A와 정렬을 시작하는 시작점인 p, 끝나는 지점인 r 총 3개이다.
시작점인p의 위치가 r보다 작게 되면 정렬할 부분이 있다는 뜻이므로 merge sort가 실행되게 된다. 위에서 확인했듯이, 배열은 절반으로 쪼개지게 되기 때문에 p와r의 절반 위치인 q를 구한다. 그리고 그 q를 기준으로 또 다시 쪼갤 수 있는 지점을 구해서 재귀적으로 쪼개가며 원소가 1개인 리스트를 만든 뒤 합치는(위 코드에서의 merge) 과정을 반복하게 된다.

4. 공간복잡도

 merge sort는 O(n)의 공간 복잡도를 가지고 있다. 하지만 배열을 정렬하는 과정에서 별도의 임시 배열이 필요하기 때문에 in-place 알고리즘은 아니다.

5. 시간복잡도

merge sort의 경우, best case, average case, worst case 모두 동일하게 O(nlogn)의 시간 복잡도를 가지고 있다.
각 단계별로 두 개의 배열로 쪼개게 되므로, 단계 수= k라고 하면 n = 2^k 라고 할 수 있고, 이걸 k를 기준으로 정리하면 k = logn이 된다. 데이터 1개마다 가져오고 비교하는 연산이 1번 씩 일어나므로 n개인 데이터에 대해서 총 2n의 연산이 필요하게 된다. 그래서 최종적으로 2n*logn이라는 식이 계산되게 되기 때문에 O(nlogn)의 시간 복잡도가 나온다고 할 수 있다.