병합 정렬 알고리즘 원리, 코드, 시간 복잡도

쉬운 말로 설명하는 원리

요소가 0개나 1개인 리스트는 이미 정렬되어 있습니다. 더 긴 리스트는 다음과 같이 처리합니다.

1. 분할(Divide): 리스트를 왼쪽 절반과 오른쪽 절반으로 나눕니다.
2. 정복(Conquer): 각 절반을 병합 정렬로 정렬합니다.
3. 결합(Combine): 정렬된 두 절반을 병합합니다. 각 절반의 첫 요소를 비교해 작은 것을 출력으로 옮기고, 한쪽이 빌 때까지 반복한 다음 다른 쪽에 남은 것을 복사합니다.

실제 작업은 모두 병합 단계에서 일어나며, 전체 길이가 n인 정렬된 두 리스트를 병합하는 데 필요한 비교는 최대 n − 1번뿐입니다.

단계별 예제

[38, 27, 43, 3, 9, 82, 10]을 정렬해 봅시다.

마지막 병합은 앞쪽 요소끼리 비교합니다. 27 대 3에서 3, 27 대 9에서 9, 27 대 10에서 10, 27 대 82에서 27, 38 대 82에서 38, 43 대 82에서 43을 꺼내고, 마지막으로 82를 복사합니다. 요소 7개에 비교는 6번입니다.

파이썬 구현

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

이 하향식 버전은 이해하기 쉽지만 슬라이스를 복사합니다. 상향식 버전은 재귀를 아예 쓰지 않습니다. 너비 1인 런을 병합한 뒤 2, 4, ... 식으로 늘려 갑니다.

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

상향식 버전은 위의 merge를 재사용합니다. 표준 라이브러리에는 정렬된 이터러블 여러 개를 지연 방식으로 병합하는 heapq.merge도 있습니다.

시간 복잡도와 공간 복잡도

점화식은 T(n) = 2T(n/2) + O(n)입니다. 재귀 트리의 각 레벨은 합쳐서 O(n)의 작업을 하고 레벨은 약 log₂ n개이므로 전체는 O(n log n)입니다. 항목이 100만 개면 약 20레벨입니다.

병합 정렬과 다른 정렬 비교

병합할 때 두 요소가 같으면 왼쪽 절반에서 꺼내므로 같은 요소의 순서가 유지되어 병합 정렬은 안정 정렬입니다. 퀵 정렬과 비교하면 최악의 경우가 O(n log n)으로 보장되지만 O(n) 추가 메모리가 필요하고 배열에서는 보통 데이터 이동이 더 많습니다. 힙 정렬과 비교하면 안정 정렬이고 메모리를 순차적으로 접근하므로 캐시와 디스크에 유리합니다.

변형과 흔한 실수

• 자연 병합 정렬은 이미 정렬된 런을 찾아 병합하므로 정렬된 입력에서 O(n)입니다. Timsort는 짧은 런에 이진 삽입 정렬을 쓰는, 개선된 자연 병합 정렬입니다.
• 작은 부분 리스트(예: 약 10~30개 미만)에서는 삽입 정렬로 전환해 오버헤드를 줄입니다.
• 연결 리스트에서는 병합 정렬에 추가 버퍼가 필요 없습니다. 병합은 노드의 연결만 바꾸기 때문에 연결 리스트를 정렬할 때 보통 이 방법을 씁니다.
• 외부 병합 정렬은 메모리에 들어가는 덩어리를 각각 정렬해 디스크에 쓴 다음 k-way 병합을 수행합니다. 데이터베이스와 GNU sort 같은 도구가 큰 파일에 이 방식을 씁니다.
• 역전 수 세기: 병합하는 동안 오른쪽 절반에서 요소를 꺼낼 때마다, 그 요소는 왼쪽 절반에 남은 모든 요소보다 작습니다.

병합 정렬을 쓰는 경우

안정 정렬이 필요하고 O(n log n) 시간이 보장되어야 할 때, 연결 리스트를 정렬할 때, 데이터가 메모리에 비해 너무 클 때 병합 정렬을 고르세요. 파이썬에서는 그냥 sorted()나 list.sort()를 호출하면 됩니다. 이들은 병합 정렬의 변형인 Timsort를 구현하므로 이미 이런 특성을 얻습니다. 병합 정렬을 직접 작성하는 것은 대표적인 면접 과제이며, 역전 수 세기나 k개의 정렬된 리스트 병합으로 확장되는 경우가 많습니다.