컴퓨터공학 300 주제 시리즈의 065번째 글이다. 전체 지도는 여기.

한 줄 요약

병합 정렬은 배열을 반으로 나눠 각각 정렬한 뒤, 정렬된 두 조각을 앞에서부터 한 번 훑어 합친다. 입력과 무관하게 Θ(n log n) 이고 안정적이지만, 배열에서는 Θ(n) 추가 메모리가 든다.

왜 필요한가

앞 글의 단순 정렬들은 Θ(n²) 이었다. n = 100만이면 비교가 수천억 번이다. 병합 정렬은 같은 입력을 약 2천만 번 비교로 끝낸다. 게다가 최악의 경우가 따로 없다. 운 나쁜 입력에서 느려지는 퀵 정렬과 다른 점이다.

병합이라는 연산 자체도 중요하다. “이미 정렬된 여러 줄을 하나로 합치기” 는 메모리에 다 안 들어가는 거대한 파일을 정렬할 때, 데이터베이스가 정렬-병합 조인을 할 때, LSM 트리가 파일들을 압축(compaction)할 때 그대로 나온다.

핵심 개념

분할, 정복, 결합

             [38 27 43 3 9 82 10]
             /                  \
      [38 27 43]            [3 9 82 10]
       /     \               /       \
    [38]  [27 43]        [3 9]     [82 10]
           /  \          /  \       /   \
        [27] [43]      [3]  [9]  [82]  [10]
    ---------------- 합치기 ----------------
        [27 43]        [3 9]      [10 82]
    [27 38 43]           [3 9 10 82]
             [3 9 10 27 38 43 82]
  1. 분할: 가운데를 기준으로 둘로 나눈다. O(1).
  2. 정복: 각 절반을 재귀적으로 정렬한다.
  3. 결합: 두 정렬된 배열의 맨 앞끼리 비교해 작은 쪽을 내보낸다. 한 쪽이 비면 나머지를 그대로 붙인다. O(n).

왜 n log n 인가

점화식은 T(n) = 2T(n/2) + Θ(n) 이다. 재귀 트리의 각 층에서 합치는 원소 수의 합은 정확히 n 이고, 층은 log₂ n 개다. 그래서 Θ(n log n). 이것은 입력이 정렬되어 있든 역순이든 무작위든 똑같다. 분할 위치가 데이터 값이 아니라 인덱스로 정해지기 때문이다.

비교 기반 정렬은 최악에 Ω(n log n) 번 비교가 필요하다는 하한이 있다. n! 가지 순서를 구분하려면 결정 트리의 높이가 log₂(n!) ≈ n log₂ n − 1.44n 이상이어야 하기 때문이다. 병합 정렬은 이 하한에 점근적으로 맞는다.

안정성과 <=

결합 단계에서 두 값이 같을 때 왼쪽을 먼저 내보내면(left[i] <= right[j]) 같은 키의 원래 순서가 유지된다. < 로 쓰면 안정성이 깨진다. 한 글자 차이다.

공간 비용

배열 병합 정렬은 합칠 때 결과를 담을 Θ(n) 보조 배열이 필요하다. 연결 리스트에서는 노드 포인터만 바꾸면 되므로 추가 배열 없이 병합할 수 있다. 그래서 연결 리스트 정렬에는 병합 정렬이 표준처럼 쓰인다.

외부 정렬

데이터가 메모리보다 클 때를 생각하자.

  1. 메모리에 들어가는 만큼 읽어 정렬한 뒤 디스크에 임시 파일(run)로 쓴다.
  2. k 개의 run 을 동시에 열고, 각 run 의 맨 앞 원소를 최소 힙에 넣는다.
  3. 힙에서 최솟값을 꺼내 출력하고, 그 원소가 나온 run 에서 다음 원소를 힙에 넣는다.

k-way 병합 한 번의 비용은 원소당 O(log k) 이다. 디스크를 순차로 읽고 쓰기 때문에 임의 접근보다 훨씬 빠르다.

오버플로 함정

중간 인덱스를 (lo + hi) / 2 로 계산하면 lo + hi 가 정수 범위를 넘을 수 있다. Joshua Bloch 는 2006년 Google 블로그 글에서 JDK 의 이진 탐색과 병합 정렬에 이 버그가 있었다고 밝혔다. 고정 폭 정수를 쓰는 언어에서는 lo + (hi - lo) / 2 로 쓴다. Python 정수는 임의 정밀도라 이 문제가 없다.

직접 해 보기

비교 횟수를 세어 n log₂ n 과 비교하고, 안정성과 k-way 병합을 확인한다. python3 로 실행해 확인했다.

import random, math, heapq

cmp = 0
def merge_sort(a):
    global cmp
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        cmp += 1
        if left[i] <= right[j]:      # <= 라서 안정 정렬
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

random.seed(0)
for n in [1024, 8192, 65536]:
    cmp = 0
    data = [random.random() for _ in range(n)]
    assert merge_sort(data) == sorted(data)
    print(f"n={n:6d} 비교={cmp:8d}  n*log2(n)={int(n*math.log2(n)):8d}")

# 안정성: 키(첫 원소)만 비교하는 래퍼
recs = [(2, "a"), (1, "b"), (2, "c"), (1, "d")]
class K:
    def __init__(s, r): s.r = r
    def __le__(s, o): return s.r[0] <= o.r[0]
print([k.r for k in merge_sort([K(r) for r in recs])])

# 이미 정렬된 여러 조각을 합치기 (외부 정렬의 마지막 단계)
chunks = [[1, 4, 9], [2, 3, 10], [5, 6, 7]]
print(list(heapq.merge(*chunks)))

출력:

n=  1024 비교=    8964  n*log2(n)=   10240
n=  8192 비교=   96221  n*log2(n)=  106496
n= 65536 비교=  965898  n*log2(n)= 1048576
[(1, 'b'), (1, 'd'), (2, 'a'), (2, 'c')]
[1, 2, 3, 4, 5, 6, 7, 9, 10]

비교 횟수는 n log₂ n 보다 조금 적다. 한 쪽이 먼저 비면 나머지는 비교 없이 붙이기 때문이다. 키가 같은 (2,’a’) 와 (2,’c’) 는 원래 순서를 지켰다. heapq.merge 는 표준 라이브러리에 들어 있는 k-way 병합이다. 입력을 전부 메모리에 올리지 않고 반복자로 받아 처리한다.

현업에서는

  • 표준 라이브러리 정렬. Python list.sort() 의 Timsort 는 병합 정렬을 뿌리로 한다. 입력에서 이미 정렬된 구간(run)을 찾아 병합하기 때문에 실제 데이터에 흔한 부분 정렬 구조를 잘 활용한다. Java 의 객체 배열 정렬도 안정 정렬을 보장한다.
  • 대용량 파일 정렬. 유닉스 sort 명령은 메모리를 넘는 입력을 임시 파일로 나눠 정렬한 뒤 병합한다. 로그 수 GB 를 정렬할 때 디스크에 임시 파일이 생기는 이유다.
  • 데이터베이스. 정렬에 쓸 메모리(PostgreSQL 의 work_mem)가 모자라면 실행 계획에 “external merge” 가 찍히고 디스크를 쓴다. 이 줄을 보면 메모리 설정이나 인덱스를 검토할 신호다.
  • 로그 합치기. 여러 노드에서 각각 시간순으로 쌓인 로그를 하나의 타임라인으로 합칠 때도 k-way 병합이다. 홈랩 클러스터에서 노드별 journal 을 한 줄로 합쳐 보는 것도 같은 원리다.

확인 문제

  1. 병합 정렬의 최선 시간 복잡도는? 삽입 정렬과 다른 이유는?
  2. 결합 단계에서 <= 를 < 로 바꾸면 무엇이 달라지는가?
  3. 정렬된 run 이 k 개, 원소가 총 n 개일 때 힙을 쓴 k-way 병합의 시간 복잡도는?
  4. mid = (lo + hi) / 2 가 문제가 되는 조건은?

풀이

  1. Θ(n log n). 분할이 값과 무관하게 일어나 이미 정렬된 입력에서도 같은 일을 한다. (Timsort 처럼 run 을 감지하는 변형은 정렬된 입력에서 Θ(n) 이다.)
  2. 같은 키일 때 오른쪽이 먼저 나가 안정성이 깨진다. 결과의 키 순서는 맞지만 동점 원소의 상대 순서가 바뀔 수 있다.
  3. 원소마다 힙 연산 O(log k) 이므로 O(n log k).
  4. lo + hi 가 정수형 최댓값을 넘을 때, 즉 고정 폭 정수를 쓰고 배열이 매우 클 때다.

더 읽을거리 (References)