병합 정렬

병합 정렬은 정렬되지 않은 리스트를 원소가 하나인 부분 리스트로 분할한 뒤, 이를 다시 정렬하며 병합하여 최종적인 정렬 리스트를 만드는 방식이다. 1945년 존 폰 노이만에 의해 고안되었으며, 1948년 헤르만 골드스타인과 폰 노이만의 보고서를 통해 상향식 병합 정렬에 대한 상세한 분석이 공개되었다. 이 알고리즘은 데이터의 크기가 커져도 성능이 일정하게 유지되는 장점이 있다.

일반적으로 사용되는 하향식(Top-down) 2-way 병합 정렬은 다음과 같은 과정을 거친다.

1. 분할(Divide): 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 리스트의 길이가 1 이하가 될 때까지 반복한다.
2. 정복(Conquer): 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
3. 결합(Combine/Merge): 정렬된 두 부분 리스트를 비교하여 하나의 정렬된 리스트로 합친다. 이때 결과는 임시 배열에 저장된다.
4. 복사(Copy): 임시 배열에 저장된 정렬 결과를 원래의 배열로 복사한다.

상향식(Bottom-up) 방식은 재귀 없이 반복문을 사용하여 작은 크기의 부분 리스트부터 시작하여 점차 병합해 나가는 방식을 취한다.

배열 [6, 5, 3, 1]을 오름차순으로 정렬하는 과정은 다음과 같다.

최종 병합 시에는 각 부분 리스트의 첫 번째 원소를 비교하여 더 작은 값을 선택해 결과 배열에 넣는 과정을 반복한다.

• 안정 정렬(Stable Sort): 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 변하지 않는다.
• 시간 복잡도: 최선, 평균, 최악의 경우 모두 $O(n \log n)$의 성능을 보인다. 이는 데이터의 초기 정렬 상태에 영향을 받지 않음을 의미한다.
• 공간 복잡도: 정렬 과정에서 정렬된 결과를 담을 추가적인 임시 배열이 필요하므로 $O(n)$의 공간 복잡도를 가진다. 이를 제자리 정렬(In-place sort)이 아닌 외적 정렬(Out-of-place sort) 방식이라고 한다.
• 데이터 접근: 연결 리스트(Linked List) 정렬에 매우 효율적이다. 연결 리스트는 임의 접근이 어렵지만 병합 정렬은 순차적인 접근만으로도 정렬이 가능하기 때문이다.

병합 정렬의 시간 복잡도는 분할 정복 원리에 의해 결정된다.

• 분할 단계: 리스트를 절반으로 나누는 과정은 이진 트리 구조를 형성하며, 전체 층수는 $\log_2 n$이 된다.
• 병합 단계: 각 층에서 모든 원소를 한 번씩 비교하며 병합하므로 각 층당 $O(n)$의 시간이 소요된다.
• 전체 시간 복잡도: 모든 층에서의 작업량을 합산하면 $n \times \log_2 n$이 되어 최종적으로 $O(n \log n)$이 된다.

힙 정렬과 비교할 때, 병합 정렬은 추가 메모리를 사용하지만 비교 횟수가 적어 실제 실행 시간에서 더 유리한 경우가 많다.

• 자연 병합 정렬(Natural Merge Sort): 입력 데이터에서 이미 정렬된 부분(run)을 찾아 활용함으로써 효율을 높인 변형이다.
• 제자리 병합 정렬(In-place Merge Sort): 추가 메모리 사용을 줄이기 위해 고안되었으나 구현이 복잡하고 일반적인 병합 정렬보다 속도가 느린 경우가 많다.
• 외부 정렬(External Sorting): 메모리에 모든 데이터를 올릴 수 없는 대용량 데이터를 정렬할 때, 데이터를 부분적으로 읽어 정렬한 뒤 병합하는 방식으로 사용된다.

장점

• 최악의 경우에도 $O(n \log n)$의 시간 복잡도를 보장한다.
• 안정 정렬이므로 데이터의 순서가 중요한 경우에 적합하다.
• 연결 리스트 정렬 시 효율적이며, 대용량 외부 정렬에 유리하다.

단점

• 추가적인 임시 배열이 필요하여 메모리 사용량이 크다($O(n)$).
• 데이터의 크기가 작을 때는 삽입 정렬 등 단순한 알고리즘보다 오버헤드가 클 수 있다.