병합 정렬

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

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

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

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

예를 들어 [6, 5, 3, 1] 배열을 정렬하는 과정은 다음과 같다.

1. 분할: [6, 5]와 [3, 1]로 나눈다.
2. 최소 단위 분할: [6], [5], [3], [1]로 각각 나뉜다.
3. 병합 및 정렬: [6]과 [5]를 비교하여 [5, 6]을 만들고, [3]과 [1]을 비교하여 [1, 3]을 만든다.
4. 최종 병합: [5, 6]과 [1, 3]의 각 원소를 비교하며 작은 순서대로 선택하여 [1, 3, 5, 6]을 완성한다.

이 과정에서 각 병합 단계마다 두 부분 리스트의 첫 원소를 비교하여 더 작은 값을 임시 배열에 넣는 방식이 사용된다.

병합 정렬은 다음과 같은 기술적 특성을 가진다.

• 안정 정렬(Stable Sort): 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 변하지 않는다.
• 시간 복잡도: 최선, 평균, 최악의 경우 모두 $O(n \log n)$의 성능을 보인다. 이는 힙 정렬과 유사하지만, 일반적으로 힙 정렬보다 비교 횟수가 적다.
• 공간 복잡도: 정렬 과정에서 정렬된 결과를 담을 추가적인 임시 배열이 필요하므로 $O(n)$의 공간 복잡도를 가진다. 이를 제자리 정렬(In-place sort)이 아닌 외적 정렬(Out-of-place sort) 방식이라고 한다.
• 데이터 크기: 데이터의 크기가 작을 때보다 큰 경우에 빠른 정렬 효과를 얻을 수 있다.

병합 정렬에는 여러 변형이 존재한다.

• 하향식(Top-down) 병합 정렬: 재귀를 사용하여 리스트를 분할하고 병합하는 가장 일반적인 형태이다.
• 상향식(Bottom-up) 병합 정렬: 재귀 없이 반복문을 사용하여 작은 크기의 정렬된 부분 리스트부터 시작하여 점차 병합한다. 연결 리스트 정렬에 적합하다.
• 자연 병합 정렬(Natural Merge Sort): 이미 정렬된 부분 리스트(run)를 찾아 병합하는 방식으로, 데이터가 부분적으로 정렬되어 있을 때 효율적이다.
• 제자리 병합 정렬(In-place Merge Sort): 추가 메모리 사용을 최소화하기 위해 제자리에서 병합을 수행하는 변형이 연구되었으나, 일반적으로 $O(n \log n)$ 시간 복잡도를 유지하면서 완전한 제자리 정렬을 구현하는 것은 복잡하다.

병합 정렬은 다음과 같은 분야에서 널리 사용된다.

• 대용량 데이터 정렬: 외부 정렬(External Sorting)의 기반 알고리즘으로 사용된다. 데이터가 메모리에 한 번에 들어오지 않을 때, 디스크에 저장된 데이터를 정렬하는 데 적합하다.
• 연결 리스트 정렬: 배열과 달리 연결 리스트는 임의 접근이 불가능하지만, 병합 정렬은 순차 접근만으로도 효율적으로 정렬할 수 있다.
• 전자 상거래: 대량의 상품 데이터를 정렬하는 데 사용된다.
• 병렬 컴퓨팅: 분할 정복 특성 덕분에 병렬 처리에 적합하여, 여러 프로세서에서 동시에 정렬을 수행할 수 있다.

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

• 분할 단계: 리스트를 절반으로 나누는 과정을 반복하므로 $O(\log n)$의 시간이 소요된다.
• 병합 단계: 각 병합 과정에서 모든 원소를 한 번씩 비교하므로 $O(n)$의 시간이 소요된다.
• 전체 시간 복잡도: $O(\log n) \times O(n) = O(n \log n)$이다.

공간 복잡도는 병합 결과를 저장할 임시 배열이 필요하므로 $O(n)$이다. 힙 정렬과 비교할 때, 병합 정렬은 추가 메모리를 사용하지만 비교 횟수가 적어 실제 실행 시간에서 더 빠를 수 있다.

장점

• 최악의 경우에도 $O(n \log n)$의 시간 복잡도를 보장한다.
• 안정 정렬이다.
• 연결 리스트 정렬에 효율적이다.
• 외부 정렬에 적합하다.

단점

• 추가적인 임시 배열이 필요하므로 공간 복잡도가 $O(n)$이다.
• 데이터의 크기가 작을 때는 삽입 정렬 등 단순한 알고리즘보다 느릴 수 있다.
• 제자리 정렬이 아니므로 메모리 사용량이 크다.