병합 정렬의 분할과 합치기

4장의 세 정렬은 모두 최악의 경우 Θ(n²)이라서, 원소가 100만 개라면 비교를 수천억 번 해야 합니다. 이 벽을 넘는 첫 번째 방법이 병합 정렬(merge sort)입니다. 병합 정렬은 리스트를 반으로 나누어 각각을 정렬한 다음, 정렬된 두 리스트를 하나로 합칩니다. 반으로 나눈 리스트를 정렬하는 일도 같은 방법으로 하므로 재귀로 자연스럽게 표현됩니다. 이렇게 문제를 작은 문제로 나누고(분할), 작은 문제를 각각 풀고(정복), 그 답을 합쳐 원래 문제의 답을 만드는(결합) 방법을 분할 정복(divide and conquer)이라고 합니다. 이 글에서는 병합 정렬의 핵심인 합치기부터 만들고, 전체 정렬이 왜 맞고 왜 빠른지를 차례로 설명합니다.

정렬된 두 리스트 합치기

정렬된 두 리스트를 하나의 정렬된 리스트로 합치는 일을 병합(merge)이라고 합니다. 두 리스트가 이미 정렬되어 있으므로, 각 리스트의 맨 앞 값이 그 리스트에서 가장 작은 값입니다. 그래서 두 맨 앞 값 가운데 작은 것이 남은 모든 값 가운데 가장 작은 값이고, 그것을 결과에 붙이면 됩니다. 값을 하나 가져온 리스트는 다음 값이 새로운 맨 앞이 되고, 같은 일을 되풀이합니다. 한쪽 리스트를 다 쓰면 다른 쪽에 남은 값들은 이미 정렬되어 있고 결과의 어떤 값보다도 작지 않으므로 그대로 뒤에 붙입니다.

[2, 4]와 [1, 3]을 합치는 과정은 다음과 같습니다.

코드에서는 i와 j가 각각 왼쪽과 오른쪽 리스트의 맨 앞 위치를 가리킵니다. 값을 가져올 때마다 원래 리스트에서 값을 지우는 대신 위치만 한 칸 옮기므로, 값 하나를 가져오는 데 드는 비용이 O(1)입니다. extend는 리스트 끝에 다른 리스트의 값들을 모두 붙이는 메서드입니다.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


print(merge([2, 4], [1, 3]))
print(merge([1, 2, 3], [7, 8]))
print(merge([], [5, 6]))

[1, 2, 3, 4]
[1, 2, 3, 7, 8]
[5, 6]

반복이 끝나면 두 리스트 가운데 적어도 하나는 다 쓴 상태이므로, 두 extend 가운데 하나는 빈 리스트를 붙입니다. 어느 쪽이 남았는지 따로 확인하지 않아도 되는 이유입니다. 값을 하나 가져올 때마다 결과가 한 칸 늘고, 비교는 값을 가져올 때만 한 번씩 하므로 길이의 합이 n인 두 리스트를 합치는 비용은 O(n)입니다. 비교는 많아야 n - 1번인데, 마지막 값은 비교 없이 붙여지기 때문입니다.

나누고, 정렬하고, 합치기

병합만 있으면 정렬은 간단합니다. 원소가 하나 이하인 리스트는 이미 정렬되어 있으므로 그대로 돌려주는 것이 기저 사례입니다. 그보다 길면 가운데에서 둘로 나누고, 두 반쪽을 각각 같은 함수로 정렬한 뒤 병합합니다.

아래 코드의 merge_sort가 병합 정렬이고, merge_sort_trace는 재귀가 어떤 순서로 나누고 합치는지 보려고 같은 일을 하면서 나눌 때와 합칠 때 출력하도록 바꾼 함수입니다. 출력은 깊이에 따라 들여 씁니다.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_sort(values):
    if len(values) <= 1:
        return list(values)
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    return merge(left, right)


def merge_sort_trace(values, depth=0):
    indent = "  " * depth
    if len(values) <= 1:
        return list(values)
    middle = len(values) // 2
    print(f"{indent}나누기 {values} -> {values[:middle]} {values[middle:]}")
    left = merge_sort_trace(values[:middle], depth + 1)
    right = merge_sort_trace(values[middle:], depth + 1)
    result = merge(left, right)
    print(f"{indent}합치기 {left} {right} -> {result}")
    return result


print(merge_sort([4, 2, 3, 1]), merge_sort([3, 1, 3]), merge_sort([]))
print(merge_sort_trace([5, 2, 4, 7, 1, 3]))

[1, 2, 3, 4] [1, 3, 3] []
나누기 [5, 2, 4, 7, 1, 3] -> [5, 2, 4] [7, 1, 3]
  나누기 [5, 2, 4] -> [5] [2, 4]
    나누기 [2, 4] -> [2] [4]
    합치기 [2] [4] -> [2, 4]
  합치기 [5] [2, 4] -> [2, 4, 5]
  나누기 [7, 1, 3] -> [7] [1, 3]
    나누기 [1, 3] -> [1] [3]
    합치기 [1] [3] -> [1, 3]
  합치기 [7] [1, 3] -> [1, 3, 7]
합치기 [2, 4, 5] [1, 3, 7] -> [1, 2, 3, 4, 5, 7]
[1, 2, 3, 4, 5, 7]

첫 줄은 merge_sort로 정렬한 세 결과입니다. 추적 출력에서는 왼쪽 반쪽 [5, 2, 4]가 끝까지 나뉘고 합쳐진 뒤에야 오른쪽 반쪽 [7, 1, 3]의 처리가 시작됩니다. 재귀 호출 merge_sort_trace(values[:middle], ...)가 끝나야 다음 줄의 오른쪽 호출로 넘어가기 때문입니다. 길이가 3인 리스트는 3 // 2 = 1에서 나뉘어 왼쪽 한 개, 오른쪽 두 개가 되는데, 이렇게 두 반쪽의 길이가 하나 차이 나도 문제는 없습니다.

왜 맞고 왜 끝나는가

병합이 맞는 이유는 이렇습니다. 반복하는 동안 결과에는 지금까지 가져온 값들이 정렬된 순서로 들어 있고, 그 값들은 아직 남은 어떤 값보다도 크지 않습니다. 매번 남은 값 가운데 가장 작은 값, 곧 두 맨 앞 값 가운데 작은 것을 붙이므로 이 사실이 유지됩니다. 반복이 끝난 뒤 남은 쪽을 통째로 붙여도 그 값들은 정렬되어 있고 결과의 값들보다 작지 않으므로, 최종 결과는 두 리스트의 모든 값을 정렬한 것입니다.

병합 정렬 전체는 재귀·기저 사례·호출 스택에서 본 귀납법으로 설명합니다. 길이가 0이나 1이면 그대로 돌려주는 것이 맞습니다. 길이가 2 이상일 때 더 짧은 리스트에 대해서는 merge_sort가 맞게 정렬한다고 가정하면, 두 반쪽이 정렬된 상태로 돌아오고, 병합이 그 둘을 맞게 합치므로 전체도 맞습니다.

끝난다는 것도 길이로 보입니다. 길이가 n ≥ 2이면 middle = n // 2는 1 이상이고 n - middle도 1 이상이므로, 두 반쪽은 모두 n보다 짧습니다. 호출할 때마다 길이가 줄어 결국 기저 사례인 길이 0이나 1에 도착합니다.

왜 O(n log n)인가

병합 정렬의 비용은 호출들을 나무 모양으로 그린 재귀 트리(recursion tree)로 따져 보면 잘 보입니다. 맨 위에는 길이 n인 호출 하나가 있고, 그 아래에 길이 n/2인 호출 둘, 그 아래에 길이 n/4인 호출 넷이 있는 식입니다. 같은 층의 호출들은 리스트를 겹치지 않게 나누어 가지므로, 한 층에서 병합하는 원소의 개수를 모두 더해도 많아야 n입니다. 병합 비용은 합치는 원소 수에 비례하므로 한 층의 비용은 O(n)입니다.

층의 개수는 길이를 반으로 줄여 1에 도착하는 횟수이므로, 입력 크기·O·Ω·Θ와 정보의 개수에서 본 것처럼 약 log₂ n입니다. 따라서 전체 비용은 층마다 O(n)씩 log₂ n개 층, 곧 O(n log n)입니다. 이 계산은 입력의 값이 어떻게 배치되어 있든 똑같이 성립하므로, 병합 정렬은 최악의 경우에도 O(n log n)입니다.

차이가 얼마나 큰지 비교 횟수로 확인해 보겠습니다. 아래 코드는 병합 정렬과 삽입 정렬이 같은 무작위 입력 1000개를 정렬하는 동안 값을 몇 번 비교하는지 셉니다.

import random


def merge_sort_count(values):
    if len(values) <= 1:
        return list(values), 0
    middle = len(values) // 2
    left, left_count = merge_sort_count(values[:middle])
    right, right_count = merge_sort_count(values[middle:])
    result = []
    i = j = 0
    count = left_count + right_count
    while i < len(left) and j < len(right):
        count += 1
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, count


def insertion_count(values):
    result = list(values)
    count = 0
    for i in range(1, len(result)):
        current = result[i]
        j = i - 1
        while j >= 0:
            count += 1
            if result[j] <= current:
                break
            result[j + 1] = result[j]
            j -= 1
        result[j + 1] = current
    return result, count


rng = random.Random(2026)
values = [rng.randrange(1_000_000) for _ in range(1000)]
print("병합 정렬", merge_sort_count(values)[1])
print("삽입 정렬", insertion_count(values)[1])

병합 정렬 8683
삽입 정렬 259579

n log₂ n은 n = 1000에서 약 1만이고, 병합 정렬의 비교 횟수 8683은 그보다 조금 적습니다. 삽입 정렬은 역순 쌍이 평균 n(n - 1)/4 ≈ 25만 개라는 앞 장의 계산대로 약 26만 번을 비교했습니다. 원소가 1000개일 때 이미 30배 가까이 차이가 나고, n이 커질수록 차이는 더 벌어집니다.

공간은 따로 따져야 합니다. 이 구현은 슬라이스로 반쪽 리스트를 복사하고 병합할 때마다 새 결과 리스트를 만들므로, 실행하는 동안 원래 입력 외에 O(n)의 공간을 더 씁니다. 재귀 깊이는 층의 개수인 O(log n)이라서, 원소가 100만 개여도 약 20층이면 되고 RecursionError를 걱정할 필요가 없습니다. 배열 안에서 값을 옮기며 병합하는 구현도 있지만, 그때도 병합할 값을 잠시 담을 O(n)의 보조 공간이 보통 필요합니다.

같은 키의 순서

merge는 두 맨 앞 값이 같으면 left[i] <= right[j]가 참이 되어 왼쪽 값을 먼저 가져옵니다. 왼쪽 리스트의 값들은 원래 입력에서 오른쪽 리스트의 값들보다 앞에 있었으므로, 키가 같은 값들은 원래 순서를 유지하고 병합 정렬은 안정 정렬이 됩니다. 이 비교를 <로 바꾸면 같을 때 오른쪽 값을 먼저 가져오게 되어 이 성질이 깨집니다. Python의 내장 정렬도 병합을 바탕으로 만든 안정 정렬입니다.

더 깊이: 병합하면서 역순 쌍 세기

버블·선택 정렬에서 역순 쌍의 개수를 셀 때는 모든 쌍을 비교해 O(n²)이 들었습니다. 병합 정렬을 조금 고치면 같은 값을 O(n log n)에 셀 수 있습니다. 역순 쌍은 두 값이 모두 왼쪽 반쪽에 있는 것, 모두 오른쪽 반쪽에 있는 것, 하나씩 나뉜 것으로 나눌 수 있습니다. 앞의 두 가지는 재귀 호출이 세어 주므로, 병합하면서 마지막 경우만 세면 됩니다.

병합 중에 오른쪽의 값 right[j]를 가져온다는 것은, 왼쪽에 남아 있는 값 left[i:]가 모두 그보다 크다는 뜻입니다. 이 값들은 원래 입력에서 right[j]보다 앞에 있었으므로 모두 right[j]와 역순 쌍을 이룹니다. 그래서 오른쪽에서 값을 가져올 때마다 len(left) - i를 더하면 됩니다.

def count_inversions(values):
    if len(values) <= 1:
        return list(values), 0
    middle = len(values) // 2
    left, left_count = count_inversions(values[:middle])
    right, right_count = count_inversions(values[middle:])
    result = []
    i = j = 0
    cross = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            cross += len(left) - i
    result.extend(left[i:])
    result.extend(right[j:])
    return result, left_count + right_count + cross


for values in [[4, 2, 6, 1, 5, 3], [6, 5, 4, 3, 2, 1], [1, 2, 3, 5, 4, 6]]:
    print(values, count_inversions(values)[1])

[4, 2, 6, 1, 5, 3] 8
[6, 5, 4, 3, 2, 1] 15
[1, 2, 3, 5, 4, 6] 1

4장에서 모든 쌍을 비교해 얻은 8, 15, 1과 같은 결과입니다. 두 사람이 매긴 순위가 얼마나 다른지를 역순 쌍의 개수로 재는 경우처럼, 이 방법은 큰 자료에서 순서의 차이를 셀 때 쓰입니다.

정리

• 병합은 정렬된 두 리스트의 맨 앞 값 가운데 작은 것을 차례로 가져와 하나의 정렬된 리스트를 만들며, 길이의 합에 비례하는 O(n)이 듭니다.
• 병합 정렬은 원소가 하나 이하이면 그대로 돌려주고, 그보다 길면 반으로 나누어 각각 재귀로 정렬한 뒤 병합합니다.
• 정확성은 병합이 남은 값 중 가장 작은 값을 계속 붙인다는 사실과 귀납법으로, 종료는 두 반쪽이 모두 원래보다 짧다는 사실로 설명합니다.
• 재귀 트리의 층마다 병합 비용이 O(n)이고 층이 약 log₂ n개라서, 입력과 상관없이 최악의 경우에도 O(n log n)입니다. 이 구현은 O(n)의 추가 공간을 씁니다.
• 같을 때 왼쪽 값을 먼저 가져오므로 안정 정렬입니다.

연습 문제

1. 병합 과정 따라가기

[1, 3, 5]와 [2, 4, 6]을 병합할 때, 각 단계에서 어느 쪽 리스트의 값을 가져오는지 순서대로 쓰고 비교 횟수를 구하세요.

2. 같을 때 오른쪽을 먼저 가져오면

merge의 left[i] <= right[j]를 left[i] < right[j]로 바꾸면 정렬 결과와 안정성은 각각 어떻게 될까요?

3. 이미 정렬된 입력에서는

삽입 정렬은 이미 정렬된 입력에서 Θ(n)으로 빨라졌습니다. 병합 정렬도 그럴까요? 본문의 merge_sort_count로 [1, 2, 3, 4, 5, 6, 7, 8], [8, 7, 6, 5, 4, 3, 2, 1], [5, 2, 4, 7, 1, 3, 2, 6]의 비교 횟수를 세어 보고 설명하세요.

다음 글 퀵 정렬·피벗·세 갈래 분할에서는 합치는 일 대신 나누는 일에 공을 들이는 또 다른 분할 정복 정렬을 봅니다. 메모리에 다 들어가지 않는 큰 자료를 병합으로 정렬하는 방법은 선택 심화: 런·다중 병합·외부 정렬에서 다룹니다.