Sort 알아보기(3) - 병합 정렬(Merge Sort)

Merge Sort

병합 정렬은 일반적인 방법으로 구현했을 때에는 안정 정렬에 속하며, 문제를 작은 2개의 문제로 분리하고 각각 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 방법인 분할 정복 알고리즘의 하나이다. 빠른 정렬로 분류되며, 퀵소트와 함께 많이 언급되는 정렬 방식이다.

정렬 과정을 살펴보면

1. 우선 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않은 경우 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 개의 리스트로 나눈다.

2. 각 부분의 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

3. 그 후 각 부분의 리스트를 다시 하나의 정렬된 리스트로 병합한다.

이 과정들을 단계별로 정리해보자면

1. 분할(Divide) : 리스트를 같은 크기의 2개의 부분 리스트로 분할한다.

2. 정복(Conquer) : 분할된 부분 리스트를 정렬한다. 만약 분할된 부분 리스트의 크기가 충분히 작지 않으면 순환 호출하여 다시 분할 정복 방법을 적용한다.

3. 결삽(Combine) : 각각 정렬된 부분 리스트들을 하나의 리스트로 병합한다.

이러한 과정에서 추가적인 리스트를 필요로 하며 병합 정렬에서 실제 정렬이 이루어지는 시점은 부분으로 나뉜 리스트를 병합하는 단계이다.

아래의 gif를 보면 윗부분이 기존에 입력된 리스트이며 아랫부분이 추가적으로 필요한 리스트라고 볼 수 있다.

병합 정렬(Merge Sort)

장점

- 안정적인 정렬 방법이기 때문에 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이던지 정렬되는 시간은 동일하다.

 

단점

- 데이터를 배열(Array)로 구성하면 임시 배열이 필요하다. 즉, 제자리 정렬이 아니다.

- 데이터의 크기가 큰 경우 이동 횟수가 많으므로 큰 시간적 낭비를 초래한다.

 

시간복잡도

- 분할 단계 : 비교 연관과 이동 연산이 수행되지 않기 때문에 영향이 없다고 본다.

 

- 합병 단계의 순환 호출의 깊이 : 데이터의 갯수 n이 2의 거듭제곱이라고 가정(n=2^k)했을 때, n = 2^3의 경우, 2^3 -> 2^2 -> 2^1 -> 2^0순으로 줄어들이 순환 호출의 깊이가 3임을 알 수 있다. 이것을 일반화하면 n=2^k의 경우, k(k=log₂n)임을 알 수 있다. (이 부분은 퀵 정렬과 동일하다.)

=> k=log₂n

- 합병 단계의 비교 연산 : 크기가 1인 부분 배열 2개를 합병하는 데에 최대 2번의 비교 연산이 필요하고 부분 배열의 쌍이 4개이므로 24 = 8번의 비교 연산이 필요하다. 다음 단계에서는 크기 2인 부분 배열 2개를 합병하는데 최대 4번 비교 연산이 필요하고 크기 4인 부분 배열 2개를 합병하는데 최대 8번, 마지막 부분 배열을 합병하는 데 8번 비교 연산이 필요하다. 이것을 일반화 하면 합병 단계에서 비교 연산은 최대 n번 수행하는 것을 알 수 있다.

- 합병 단계의 순환 호출의 깊이 * 각 합병 단계의 비교 연산 = nlog₂n

 

- 이동 단계의 순환 호출의 깊이 : 합병 단계의 수 만큼 필요하기 때문에 k=log₂n이 된다.

- 각 합병 단계의 이동 연산 : 임시 리스트를 복사했다가 다시 가져오므로 이동 연산은 요소의 갯수가 n인 경우, 데이터 이동이 2n번 발생한다.

- 이동 단계의 순환 호출의 깊이 * 각 합병 단계의 이동 연산 = 2nlog₂n

- T(n) = nlog₂n(합병) + 2nlog₂n(이동) = 3nlog₂n => O(nlog₂n)

정렬 시간복잡도 비교

참고 사이트

- https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

- https://jinhyy.tistory.com/9