Merge Sort

비교 기반 정렬 알고리즘인 합병 정렬(merge sort)은, 재귀를 이용하는 분할 정복 알고리즘이다.

분할 정복 알고리즘(divide and conquer algorithm): 해결하기 어려운 문제를 작은 문제로 분할해 해결하는 방식의 알고리즘이다. 주로 재귀 함수로 구현하며 대표적인 예가 합병 정렬이다.

분할은 배열을 쪼개는 것이고, 정복은 분할한 배열을 정렬하면서 하나로 합병하는 것을 의미한다. 그래서 정렬하려는 배열을 크기가 0 또는 1이 될 때까지 절반씩 분할한다. 분할된 각각의 배열은 다시 하나의 배열로 합쳐지면서 정렬을 수행한다.

분할

예를 들어 아래와 같이 배열 [8, 3, 2, 1, 7, 6, 4, 5]의 합병 정렬을 수행 하려면, 먼저 재귀함수를 호출해 아래 그림의 Level3 과 같이 배열 크기가 1 이하가 될 때까지 배열을 분할한다.

합병

이제, 분할을 마친 각 배열을 다시 하나로 합병하면서 정렬을 수행하여야 한다. 이 때 합병하려는 두 배열과, 두 배열의 합친 크기의 빈 배열이 필요하다. 빈 배열은 정렬을 위하여 사용된다.

각각의 배열은, 정렬이 완료된 상태에서 합병을 수행하며, 각 배열의 앞에 있는 요소부터 비교하면서 정렬한다. 만약 오름차순이면 두 배열의 앞에 있는 요소 중 작은 숫자를 빈 배열에 놓고, 내림차순이면 큰 숫자를 빈 배열에 넣는다.

배열 합병 시 각 배열의 요소들이 정렬이 완료된 상태에서 합병을 시도해야 하는 이유는 정렬된 두 배열을 병합할 때는 각 배열의 맨 앞 원소만 비교하면 되기 때문이다. 만약 정렬되지 않은 배열이라면 모든 원소를 다 비교해야 해서 매우 비효율적이다.

만약 오름차순인 경우 위 그림의 Level2 에 해당하는 [7, 6] [4, 5] 에 대하여 각 배열에 정렬을 수행한 후, 정렬된 배열인 [6, 7] [4, 5]에 대하여 합병을 진행한다면 합병 방식은 아래 그림과 같다.

[6, 7]과 [4, 5]로 된 두 배열을 정렬하기 위하여 우측에 크기가 4인 빈 배열을 준비한다. -> 두 배열의 첫 번째 요소인 6과 4를 비교했을 때, 4가 작으므로 기존 배열에서 4를 제거하고 빈 배열에 4를 삽입한다.
기존 배열에서 크기가 작았던 4를 제거하고 빈 배열에 4가 삽입 완료 되었다면, 두 번째 비교를 수행한다. [6, 7]과 [5] 배열에서 각 배열의 첫 번째 숫자인 6과 5를 비교했을 때, 5가 작으므로 기존 배열에서 5를 제거하고 새로운 배열에 5를 삽입한다.
기존 배열에서 또다시 크기가 작았던 5를 제거하고 빈 배열의 다음 요소에 5가 삽입 완료 되었다면, 세 번째 비교를 수행한다. [6, 7]과 빈 배열만 남았으므로 기존 배열에서 첫 번째 항목인 6을 제거하고, 새로운 배열에 곧바로 6을 삽입한다.
새로운 배열에 배열의 첫 번째 항목인 6이 추가로 삽입 되었다면, 마지막 비교를 수행한다. [7]과 빈 배열만 남았으므로 기존 배열에서 7을 삭제하고, 새로운 배열에 곧바로 7을 삽입한다.

위와 같은 프로세스를 통하여 기존 배열의 아이템들은 삭제되고 새로운 배열에 모든 아이템들이 정렬된 것을 확인할 수 있다.

위와 같은 방식으로, 분할한 배열을 다시 합병하면서 정렬하면 된다. 연산이 끝나면 오름차순으로 정렬된 하나의 배열을 얻을 수 있게 된다.

결론

합병 정렬의 시간 복잡도는 O(n log n)으로, 수행 시간 면에서 효율적이다. O(n)은 배열이 정렬되는 데 걸리는 시간 복잡도이고, O(log n)은 배열의 분할 또는 합병 시 걸리는 시간 복잡도이다. 합병 단계에서 배열의 정렬이 일어나므로, 합병 정렬하는 데에는 총 O(n log n)이라는 시간 복잡도가 소요된다.

배열이 정렬되는 데 걸리는 시간 복잡도: O(n)
배열의 분할 또는 합병 시 걸리는 시간 복잡도: O(log n)
총 시간 복잡도: O(n) x O(log n) = O(n log n)

위와 같이, 합병 정렬(merge sort)은 최악의 경우에도 O(n log n)을 보장하기 때문에 대용량 데이터 정렬에 적합하다고 판단할 수 있다.