병합 정렬

병합 정렬은 뒤섞인 값을 작은 것부터 순서대로 늘어놓아 줍니다. 목록을 잘게 쪼갠 뒤 정렬된 조각 둘을 하나로 합치는 일을 되풀이합니다. 값이 어떻게 섞여 있든 걸리는 시간이 늘 비슷합니다.

상세

번호 순으로 정리된 시험지 두 묶음을 한 묶음으로 합친다고 해 봅시다. 두 묶음 맨 위 장만 보고 번호가 작은 쪽을 집어 옆에 차례로 쌓습니다. 이걸 되풀이하면 두 묶음을 한 번 훑는 것으로 끝납니다.

병합 정렬은 이 합치기를 정렬의 전부로 삼습니다. 이름의 「병합」이 합친다는 뜻입니다. 영어로는 merge sort 라고 부릅니다.

넣는 것은 서로 크기를 견줄 수 있는 값의 목록입니다. 나오는 것은 같은 값들을 작은 것부터 늘어놓은 목록입니다. 이렇게 값을 순서대로 늘어놓는 일을 정렬이라고 합니다.

정렬된 두 조각을 합치는 병합

병합 정렬이 하는 일은 거의 다 이 합치기에서 일어납니다. 합치기는 이미 정렬된 두 조각을 받아 정렬된 한 조각을 내줍니다.

규칙은 하나입니다. 두 조각의 맨 앞 값을 견주어 작은 쪽을 꺼내 결과 뒤에 붙입니다. 꺼낸 조각은 다음 값이 맨 앞이 됩니다.

아래 표는 1 · 2 · 5 · 7 과 3 · 4 · 6 · 8 을 합치는 과정입니다. 한 줄이 꺼내기 한 번입니다.

마지막 줄에서 왼쪽이 먼저 비었습니다. 한쪽이 비면 더 견줄 것이 없습니다. 남은 쪽을 순서대로 뒤에 붙이면 끝납니다.

값 여덟 개를 합치는 데 견줌은 일곱 번이었습니다. 마지막 8 은 견줄 상대 없이 붙였기 때문입니다. 값마다 한 번씩만 꺼내므로 합치기 한 번에 드는 시간은 두 조각 길이의 합에 비례합니다.

같은 규칙을 파이썬으로 옮기면 이렇습니다. i 와 j 는 왼쪽과 오른쪽 조각에서 지금 맨 앞이 몇 번째인지를 가리킵니다.

def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        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

merge([2, 5], [1, 7])  # [1, 2, 5, 7]

while 은 두 조각에 모두 값이 남아 있는 동안 도는 반복입니다. 반복이 끝나면 아래 두 줄이 남은 쪽을 붙입니다. 이미 빈 쪽은 붙일 것이 없으므로 두 줄을 다 적어 두어도 됩니다.

견줌이 < 가 아니라 <= 인 것에는 이유가 있습니다. 두 값이 같으면 왼쪽 것을 먼저 꺼냅니다. 이 선택이 뒤에 나오는 「같은 값의 순서」를 지켜 줍니다.

쪼개고 합치는 전체 흐름

합치기는 정렬된 조각을 받아야 돕니다. 그 조각은 어디서 오나를 푸는 것이 쪼개기입니다. 목록을 반으로 가릅니다. 가른 조각을 또 반으로 가릅니다.

값이 하나만 남은 조각은 견줄 상대가 없습니다. 그래서 이미 정렬된 조각입니다. 쪼개기는 이 조각이 나올 때까지 내려갑니다.

그다음 방향을 바꿔 이웃한 두 조각씩 합치며 올라옵니다. 아래 그림은 값 여덟 개가 그렇게 정렬되는 과정을 한 층에 한 줄씩 보입니다. 대괄호 하나가 조각 하나입니다.

flowchart TD
    subgraph 쪼개기["쪼개기 · 견줌 없음"]
        S0["[5 2 7 1 6 3 8 4]"]
        S1["[5 2 7 1] [6 3 8 4]"]
        S2["[5 2] [7 1] [6 3] [8 4]"]
        S3["[5] [2] [7] [1] [6] [3] [8] [4]"]
    end
    subgraph 합치기["합치기 · 층마다 여덟 번 꺼낸다"]
        M2["[2 5] [1 7] [3 6] [4 8]"]
        M1["[1 2 5 7] [3 4 6 8]"]
        M0["[1 2 3 4 5 6 7 8]"]
    end
    S0 -->|"반으로 쪼갠다"| S1
    S1 -->|"반으로 쪼갠다"| S2
    S2 -->|"반으로 쪼갠다"| S3
    S3 -->|"둘씩 합친다"| M2
    M2 -->|"둘씩 합친다"| M1
    M1 -->|"둘씩 합친다"| M0

쪼개는 동안에는 값을 견주지 않습니다. 위치만 반으로 나눌 뿐입니다. 견줌은 모두 올라오며 합치는 동안 일어납니다.

합치기의 마지막 단계는 [1 2 5 7] 과 [3 4 6 8] 을 합칩니다. 앞 절의 표가 이 과정입니다. 층마다 같은 규칙이 조각 크기만 바꿔 되풀이됩니다. 이처럼 문제를 작은 같은 문제로 쪼개 풀고 답을 합치는 설계를 분할 정복이라고 합니다.

쪼갠 조각을 정렬하는 일은 원래 문제와 모양이 같습니다. 그래서 코드로는 함수가 자기 자신을 다시 부르는 재귀로 적는 것이 흔합니다.

def merge_sort(xs):
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left = merge_sort(xs[:mid])
    right = merge_sort(xs[mid:])
    return merge(left, right)

merge_sort([5, 2, 7, 1])  # [1, 2, 5, 7]

merge_sort 는 목록을 반으로 가른 두 쪽에 자신을 다시 부릅니다. 돌아온 두 쪽은 정렬돼 있으므로 앞의 merge 로 합칩니다. 값이 하나 이하면 더 가르지 않고 그대로 돌려줍니다.

걸리는 시간

시간은 두 수를 곱하면 나옵니다. 한 층을 합치는 데 드는 일과 층의 개수입니다.

한 층에서는 모든 값을 한 번씩 꺼냅니다. 앞 그림에서 합치기 층마다 여덟 번씩 꺼냈습니다. 값이 n 개면 한 층의 일은 n 에 비례합니다.

층의 개수는 n 을 1 이 될 때까지 반으로 나눈 횟수입니다. 이 횟수를 log n 이라고 적습니다. 여덟 개는 세 번 나누면 하나가 되므로 세 층입니다. 백만 개는 스무 번쯤입니다.

둘을 곱하면 n log n 입니다. 빅오 표기법으로 O(n log n) 이라고 적습니다. 빅오 표기법은 값의 개수가 늘 때 비용이 어떤 모양으로 따라 느는지를 적는 약속입니다.

값을 하나씩 제자리에 끼워 넣는 삽입 정렬은 최악일 때 O(n²) 입니다. 아래 표는 두 모양이 값의 개수에 따라 얼마나 벌어지는지를 어림으로 보입니다.

값이 백만 개면 n log n 쪽은 이천만 번쯤 일합니다. n² 쪽은 조 단위로 일합니다. 값이 많을수록 차이가 커집니다.

최악일 때와 보통일 때

병합 정렬은 최악일 때와 보통일 때가 똑같이 O(n log n) 입니다. 목록을 가르는 위치가 값과 상관없이 늘 한가운데이기 때문입니다. 값이 어떻게 섞여 있든 층의 개수가 같습니다.

퀵 정렬과 견주면 이 성질이 드러납니다. 퀵 정렬은 기준값 하나를 골라 그보다 작은 값과 큰 값으로 목록을 가르는 정렬입니다. 보통은 O(n log n) 입니다.

그런데 기준값이 계속 가장 작은 값이나 가장 큰 값으로 뽑히면 한쪽이 거의 비게 갈립니다. 그러면 층이 n 개까지 늘어나 O(n²) 이 됩니다. 병합 정렬은 가르는 방식이 값을 안 보므로 이런 경우가 생기지 않습니다.

값끼리 견주기만 해서 정렬하는 방법은 최악일 때 n log n 보다 적게 견줄 수 없습니다. 이런 정렬을 비교 정렬이라고 부릅니다. 병합 정렬은 최악일 때도 이 바닥에 붙어 있습니다.

추가로 드는 메모리

합치기는 결과를 담을 새 목록이 필요합니다. 두 조각을 읽으면서 같은 곳에 결과를 덮어쓰면 아직 안 읽은 값을 지워 버리기 때문입니다.

그래서 배열을 정렬하면 원래 크기만큼의 공간이 더 듭니다. 이 추가 공간을 O(n) 이라고 적습니다. 백만 개를 정렬하면 백만 칸짜리 배열이 하나 더 필요하다는 뜻입니다.

추가 공간 없이 원래 배열 안에서 값을 맞바꾸며 정렬하는 방식을 제자리 정렬이라고 합니다. 힙 정렬이 그렇습니다. 메모리가 빠듯하면 이 차이가 알고리즘을 고르는 기준이 됩니다.

연결 리스트는 사정이 다릅니다. 연결 리스트는 값마다 다음 값을 가리키는 연결을 들고 있는 목록입니다. 합칠 때 값을 옮기지 않고 연결만 바꿔 이으면 되므로 새 목록이 필요 없습니다.

재귀로 적으면 호출이 쌓이는 공간도 듭니다. 호출은 층의 개수만큼 쌓이므로 O(log n) 입니다. 배열이 쓰는 O(n) 에 비하면 작습니다.

같은 값의 순서를 지키는 성질

정렬 기준이 같은 값이 여럿일 때, 원래 목록에서의 앞뒤 순서를 그대로 지키는 정렬을 안정 정렬이라고 합니다. 병합 정렬은 안정 정렬입니다.

이 성질이 쓸모 있는 경우는 정렬을 두 번 할 때입니다. 주문 목록을 시각 순으로 정렬해 두었다가 금액 순으로 다시 정렬한다고 해 봅시다.

금액 순으로 다시 정렬하면 3,000 원 주문이 맨 앞에 옵니다. 5,000 원인 주문 두 건은 기준이 같습니다. 안정 정렬은 이 둘을 원래대로 09:00 → 09:20 순서로 남깁니다.

결과는 금액 순이면서 금액이 같으면 시각 순입니다. 두 기준으로 정렬한 효과를 정렬 두 번으로 얻습니다. 안정 정렬이 아니면 같은 금액끼리의 시각 순서가 뒤섞일 수 있습니다.

병합 정렬이 안정한 까닭은 앞의 <= 에 있습니다. 같은 값을 만나면 언제나 왼쪽 조각의 것을 먼저 꺼냅니다. 왼쪽 조각은 원래 목록에서도 앞쪽에 있던 값들입니다.

메모리에 다 안 들어가는 데이터

합치기는 두 조각을 앞에서부터 한 번씩 훑기만 합니다. 조각 안의 아무 위치로 건너뛸 일이 없습니다. 이 성질 덕분에 조각이 메모리가 아니라 디스크의 파일이어도 합칠 수 있습니다.

정렬할 데이터가 메모리보다 크면 이렇게 합니다. 메모리에 들어갈 만큼씩 잘라 각각 정렬해 디스크에 씁니다. 그다음 정렬된 파일들을 앞에서부터 조금씩 읽으며 합칩니다. 이 방식을 외부 정렬이라고 부릅니다.

flowchart TD
    A["메모리보다 큰 파일"] -->|"메모리에 들어갈 만큼씩 자른다"| B
    subgraph B["조각마다 메모리에서 정렬해 디스크에 쓴다"]
        B1["정렬된 파일 1"]
        B2["정렬된 파일 2"]
        B3["정렬된 파일 3"]
    end
    B1 --> M["세 파일의 맨 앞 값을 견주며 합친다"]
    B2 --> M
    B3 --> M
    M --> R["정렬된 파일 하나"]

그림에서 합치기는 두 조각이 아니라 세 조각을 한꺼번에 합칩니다. 이렇게 여러 조각을 한 번에 합치는 것을 다중 병합이라고 합니다. 규칙은 같습니다. 모든 조각의 맨 앞 값 가운데 가장 작은 것을 꺼냅니다.

조각이 많으면 맨 앞 값들 가운데 가장 작은 것을 매번 훑어 찾기가 번거롭습니다. 그래서 가장 작은 값을 빨리 꺼내 주는 우선순위 큐에 맨 앞 값들을 담아 둡니다.

데이터베이스는 ORDER BY 로 정렬할 결과가 메모리보다 크면 이 방식을 씁니다.

LSM 트리로 저장하는 데이터베이스도 같은 합치기를 씁니다. LSM 트리는 들어온 쓰기를 메모리에 모았다가 키 순으로 정렬된 파일로 한꺼번에 내려쓰는 저장 구조입니다. 내려쓸 때마다 정렬된 파일이 하나씩 쌓입니다. 이름은 Log-Structured Merge-tree 의 줄임말입니다.

쌓인 파일 하나하나가 SSTable(Sorted String Table, 정렬된 문자열 테이블)입니다. 파일이 많아지면 키 하나를 찾을 때 여러 파일을 뒤져야 하므로 여럿을 하나로 합칩니다. 이 일이 컴팩션입니다. 병합 정렬의 합치기 단계와 같은 일입니다.

다른 정렬과 견준 병합 정렬

아래 표는 자주 견주는 세 정렬을 시간, 추가 공간, 안정성으로 나란히 놓은 것입니다.

표의 O(1) 은 값이 아무리 많아도 추가 공간이 몇 칸으로 일정하다는 뜻입니다. 퀵 정렬의 O(log n) 은 재귀 호출이 쌓이는 공간입니다.

병합 정렬이 내주는 것은 추가 공간입니다. 대신 시간 보장과 안정성을 얻습니다. 병합 정렬을 고르는 경우는 셋입니다. 최악일 때 시간을 보장해야 할 때, 같은 값의 순서를 지켜야 할 때, 데이터가 메모리를 넘을 때입니다.

조각에 든 값이 몇십 개 이하로 줄면 재귀 호출을 더 이어 가는 비용이 상대적으로 커집니다. 값이 적으면 단순한 삽입 정렬이 함수를 더 부르고 조각을 나누는 수고보다 빨리 끝납니다. 그래서 작은 조각은 삽입 정렬로 마무리하는 구현이 흔합니다.

팀 정렬은 작은 조각을 삽입 정렬로 처리하는 데 더해, 목록 안에 이미 정렬된 구간을 찾아 그 구간을 조각으로 삼습니다. 그 조각들을 병합 정렬처럼 합칩니다.

관련 항목

병합 정렬이 속하는 상위 분류

알고리즘 · 정렬 알고리즘 · 정렬 · 비교 정렬 · 분할 정복

같은 정렬 문제를 푸는 다른 방법

퀵 정렬 · 힙 정렬 · 삽입 정렬 · 선택 정렬 · 버블 정렬 · 기수 정렬 · 계수 정렬 · 셸 정렬

병합 정렬을 뼈대로 삼은 변형

팀 정렬 · 외부 정렬 · 다중 병합 · 상향식 병합 정렬 · 자연 병합 정렬 · 제자리 병합 정렬

병합 정렬이 지키는 성질

안정 정렬 · 전순서 · 불변 조건 · 결정적 알고리즘

병합 정렬의 비용을 적는 표기

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 로그 함수 · 점화식 · 마스터 정리 · 비교 정렬 하한

병합 정렬이 도는 자료구조

배열 · 연결 리스트 · 우선순위 큐 · 이진 힙 · 호출 스택 · 재귀

병합 정렬의 합치기를 쓰는 저장 구조

LSM 트리 · SSTable · 컴팩션 · 정렬 병합 조인 · 순차 읽기 · 이진 탐색