적응형 병합 정렬(Adaptive Merge Sort)이란?
적응형 병합 정렬은 일반 병합 정렬(Merge Sort)과 마찬가지로 정렬된 부분 리스트를 병합하는 방식으로 동작합니다. 하지만 결정적인 차이점은, 초기 부분 리스트의 크기를 항상 1로 시작하는 것이 아니라 입력 리스트에 이미 존재하는 정렬 상태(순서)를 활용하여 부분 리스트의 크기를 결정한다는 점입니다. 예를 들어 다음 그림과 같은 리스트를 살펴보겠습니다.
이 리스트는 두 개의 정렬된 부분 리스트로 구성되어 있습니다.
- 부분 리스트 1: 16, 15, 14, 13
- 부분 리스트 2: 9, 10, 11, 12
부분 리스트 1은 역순(reverse order)으로 정렬되어 있습니다. 따라서 그림과 같이 부분 리스트 1을 뒤집어 올바른 순서로 만듭니다.
부분 리스트들을 모두 찾았다면 병합(merge) 과정이 시작됩니다. 이 예제에서는 부분 리스트가 2개뿐이므로 병합 단계는 단 한 번만 필요합니다. 병합 결과는 다음 그림과 같습니다.
설계 아이디어
- 먼저 원하는 순서대로 또는 역순으로 이미 정렬되어 있는 부분 리스트를 찾습니다.
- 역순으로 정렬된 부분 리스트가 존재한다면, 첫 번째 요소와 마지막 요소, 두 번째 요소와 뒤에서 두 번째 요소를 교환하는 방식으로 해당 리스트를 뒤집습니다.
- 부분 리스트들을 계속 병합하여 새로운 부분 리스트를 만들고, 하나의 부분 리스트만 남을 때까지 이 과정을 반복합니다.
적응형 병합 정렬 분석
적응형 병합 정렬은 크기 1짜리 부분 리스트부터 시작하는 대신, 이미 원하는 순서 또는 역순으로 정렬되어 있는 부분 리스트를 탐색합니다. 처음 발견되는 부분 리스트의 크기는 최소 2, 최대 m입니다(여기서 m은 전체 요소의 개수).
다만 부분 리스트가 역순으로 정렬되어 있는 경우에는 병합 연산을 시작하기 전에 리스트를 먼저 뒤집어야 합니다. 리스트를 뒤집는 작업에는 m/2번의 교환(exchange) 연산이 필요합니다.
최선의 경우(Best Case)
리스트가 이미 오름차순으로 정렬되어 있거나 역순으로 정렬되어 있다면, 적응형 병합 정렬은 전체 리스트를 하나의 부분 리스트로 간주하므로 병합 연산이 전혀 필요하지 않습니다. 다만 리스트가 이미 정렬되어 있음을 확인하는 데 O(m)번의 비교 연산이 소요되며, 역순으로 정렬된 경우에는 추가로 m/2번의 교환 연산이 필요합니다. 이러한 특성 덕분에 적응형 병합 정렬은 리스트가 역순으로 정렬된 경우에도 효율적으로, 즉 '적응적으로' 동작할 수 있습니다.
따라서 최선의 경우 시간 복잡도는 다음과 같이 계산됩니다.
T(m) = (m-1)+(m/2)
T(m) = (2m-2+m)/2
T(m) = O(m).
단, 적응형 병합 정렬은 일반 병합 정렬에 비해 O(m)의 추가 메모리 공간을 필요로 한다는 점에 유의해야 합니다.
최악의 경우(Worst Case)
적응형 병합 정렬은 원하는 순서 또는 역순으로 정렬된 부분 리스트를 찾으려고 시도하지만, 최악의 경우에는 부분적인 순서조차 전혀 존재하지 않습니다. 이때 초기에 발견되는 부분 리스트의 크기는 2가 됩니다. 부분 리스트를 모두 찾은 후에는 병합 과정이 시작됩니다.
- 크기 2인 부분 리스트들을 병합하면 크기 4인 정렬된 부분 리스트가 생성됩니다.
- 크기 4인 부분 리스트들을 병합하면 크기 8인 정렬된 부분 리스트가 생성됩니다.
- 이 병합 과정은 2k < m을 만족하는 동안 계속됩니다. 여기서 k는 k번째 병합 단계를 의미합니다.
결국 최악의 경우 적응형 병합 정렬의 병합 단계 수는 일반 병합 정렬과 동일하므로, 시간 복잡도 역시 병합 정렬과 같습니다.
T(m) = O(m log m).