yeolyi.com성열의 컴퓨터공학

병합 정렬

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

숫자 100만 개를 작은 수부터 늘어놓으려 합니다. 선택 정렬로는 비교를 5,000억 번쯤 해야 해서, 1초에 10억 번 비교한다 쳐도 8분이 넘게 걸립니다. 재귀로 문제를 작게 줄여 더 적게 비교할 수는 없을까요?

정렬된 두 줄 합치기

쉬운 문제부터 풀어 봅시다. 이미 작은 수부터 정렬된 줄이 두 개 있습니다. 이 둘을 하나의 정렬된 줄로 합치려면 어떻게 할까요?

가장 작은 수는 반드시 두 줄 중 한 줄의 맨 앞에 있습니다. 그러니 맨 앞끼리만 비교해 작은 쪽을 꺼내는 일을 반복하면 됩니다.

왼쪽 줄
381421
오른쪽 줄
591227
합친 줄

두 줄 모두 작은 수부터 정렬되어 있습니다.비교 0번

비교할 때마다 수가 하나씩 내려가니, 두 줄 길이의 합이 m이면 비교는 많아야 m − 1번, O(m)입니다.

나누고 합치기

정렬된 두 줄은 어디서 구할까요? 여기서 재귀를 씁니다. 배열을 반으로 나눠 각 절반을 같은 방법으로 정렬한 다음, 방금 본 방법으로 합칩니다. 값이 하나뿐인 조각은 이미 정렬된 것이니 기저 사례입니다.

1#include <stdio.h>
2
3int arr[6] = {5, 2, 7, 1, 6, 3};
4// 합친 줄을 잠시 담는 곳
5int tmp[6];
6
7// arr[lo]~arr[mid - 1]과
8// arr[mid]~arr[hi - 1]을 합친다
9void merge(int lo, int mid, int hi) {
10 int i = lo;
11 int j = mid;
12 int k = lo;
13 // 두 줄 모두 남아 있는 동안
14 while (i < mid && j < hi) {
15 // 맨 앞끼리 비교해 작은 쪽을 꺼낸다
16 if (arr[i] <= arr[j]) {
17 tmp[k] = arr[i];
18 k++;
19 i++;
20 } else {
21 tmp[k] = arr[j];
22 k++;
23 j++;
24 }
25 }
26 // 남은 줄을 뒤에 붙인다
27 while (i < mid) {
28 tmp[k] = arr[i];
29 k++;
30 i++;
31 }
32 while (j < hi) {
33 tmp[k] = arr[j];
34 k++;
35 j++;
36 }
37 for (k = lo; k < hi; k++) {
38 arr[k] = tmp[k];
39 }
40}
41
42// arr[lo]~arr[hi - 1]을 정렬한다
43void merge_sort(int lo, int hi) {
44 // 하나 이하면 이미 정렬됨
45 if (hi - lo <= 1) {
46 return;
47 }
48 // 가운데 위치
49 int mid = (lo + hi) / 2;
50 // 앞 절반, 뒤 절반 정렬
51 merge_sort(lo, mid);
52 merge_sort(mid, hi);
53 // 앞에서 본 '정렬된 두 줄 합치기'
54 merge(lo, mid, hi);
55}
56
57int main(void) {
58 merge_sort(0, 6);
59 for (int i = 0; i < 6; i++) {
60 printf("%d ", arr[i]);
61 }
62 printf("\n");
63 return 0;
64}

변수 없음
출력 없음

재생하며 lo와 hi 사이 구간이 반씩 줄었다가 합쳐지는 모습을 봅시다.

이처럼 문제를 작은 문제로 나누고, 각각 풀고, 그 답을 합치는 방법을 분할 정복(divide and conquer)이라 합니다. 분할 정복으로 정렬하는 이 방법이 병합 정렬(merge sort)입니다.

처음 배열
27143834521933

먼저 반씩 나눕니다.비교 0번

층마다 비교 횟수를 봅시다.

한 칸짜리 조각까지 나뉜 뒤 이웃끼리 합쳐 올라갑니다. 데모는 같은 층을 한꺼번에 합쳤지만, 실제 재귀 호출과 순서만 다를 뿐 비교는 같습니다.

비교 횟수

한 층에서는 모든 값이 한 번씩 합친 줄로 내려가니 비교는 n번을 넘지 않습니다. 층은 반으로 나누기를 몇 번 해야 한 칸이 되는지, 즉 log₂ n개입니다.

그래서 전체 비교는 n log₂ n번을 넘지 않습니다. 병합 정렬은 O(n log n)입니다. 시간 복잡도 글의 데모에서 예가 비어 있던 줄입니다. 숫자 100만 개도 비교가 2,000만 번을 넘지 않아 0.02초면 됩니다.

섞인 숫자 n 100개
선택 정렬비교 4,950번
병합 정렬비교 538번

병합 정렬이 약 9.2배 적게 비교합니다.

n이 8이면 선택 정렬 28번, 병합 정렬 15번으로 차이가 작지만, 2,000이면 약 100배가 됩니다.

공짜는 아닙니다. 합친 결과를 담을 줄(코드의 tmp)이 따로 필요해 원래 배열만큼의 메모리를 더 씁니다.

도전 문제

서로 다른 값 8개를 글의 merge_sort로 정렬합니다. 두 줄을 합칠 때는 맨 앞끼리 한 번 비교해 작은 쪽을 내리고, 한 줄이 비면 남은 줄은 비교 없이 그대로 붙입니다. 처음 순서를 잘 고르면 비교는 모두 몇 번까지 줄어들까요? 숫자로 답하세요.