분할 정복 — 나누어 풀고, 정렬의 한계를 증명하다

큰 문제를 한 번에 푸는 대신, 똑같이 생긴 작은 문제 몇 개로 쪼갠다. 작은 것들을 풀어 다시 합치면 원래 문제가 풀린다. 이 단순한 발상이 정렬의 이론적 한계까지 우리를 데려간다.

분할 정복의 세 단계

분할 정복(divide and conquer) 은 재귀의 가장 강력한 활용처다. 큰 문제를 그대로 마주하지 않고, 다음 세 단계로 푼다.

1. 나누기(divide) — 입력을 더 작은 같은 종류의 문제로 쪼갠다.
2. 풀기(conquer) — 작아진 문제를 (대개 재귀로) 푼다.
3. 합치기(combine) — 작은 문제들의 답을 모아 원래 문제의 답을 만든다.

이 구조가 성립하려면 한 가지 전제가 필요하다.

나누고 합치는 두 작업이 충분히 싸다면, 분할 정복은 종종 단순 반복보다 훨씬 빠르다. 그 이유를 가장 또렷하게 보여 주는 예가 merge sort다.

---

Merge Sort, 다시 보기

merge sort는 분할 정복의 교과서적 예다. 배열을 반으로 나눠 각각 정렬하고, 정렬된 두 조각을 합친다.

void sort(int a[], int n) {
    if (n <= 1) return;     // 기저 사례: 크기 1은 이미 정렬됨
    int h = n / 2;
    sort(a, h);             // 나누기 + 풀기: 왼쪽 절반
    sort(a + h, n - h);     // 나누기 + 풀기: 오른쪽 절반
    std::vector<int> b(n);  // 보조 배열 (표준 C++에서 int b[n]은 가변 길이 배열이라 비표준)
    merge(a, h, n, b.data());  // 합치기: 정렬된 두 절반을 병합
}

세 단계가 그대로 드러난다. sort(a, h) 와 sort(a + h, n - h) 가 나누고 푸는 부분이고, merge 가 합치는 부분이다. 병합은 정렬된 두 배열을 앞에서부터 훑으며 작은 값을 골라 담는 두 포인터 연산으로, 길이 $n$ 을 합치는 데 $O(n)$ 이 든다.

동작 원리와 올바름 증명(루프 불변식·강한 귀납법), 그리고 quick sort와의 비교는 정렬 알고리즘 포스트에서 자세히 다뤘다. 여기서는 분할 정복의 비용에 집중한다.

병합 비용 $n$ 과 절반짜리 재귀 호출 두 번이 모여 점화식이 세워진다.

$$T(n) = 2T\!\left(\frac{n}{2}\right) + n$$

---

점화식을 대입법으로 풀기

재귀 트리나 마스터 정리로도 이 점화식을 풀 수 있지만, 여기서는 대입법(substitution method) 을 써 보자. 해의 모양을 먼저 추측하고, 점화식에 그대로 넣어 계수가 맞는지 확인하는 방법이다.

해가 다음 형태라고 추측한다.

$$T(n) = a\,n \log n + b\,n + c$$

이 추측을 점화식 $T(n) = 2T(n/2) + n$ 의 우변에 대입한다. 우변의 $T(n/2)$ 자리에 같은 식을 $n/2$ 에 대해 써 넣으면,

$$2\left[a\,\frac{n}{2}\log\frac{n}{2} + b\,\frac{n}{2} + c\right] + n = a\,n \log\frac{n}{2} + b\,n + 2c + n$$

여기서 $\log(n/2) = \log n - 1$ 이므로 $a\,n\log(n/2) = a\,n\log n - a\,n$ 이다. 풀어 쓰면,

$$a\,n \log n - a\,n + b\,n + 2c + n$$

이 값이 좌변 $T(n) = a\,n\log n + b\,n + c$ 와 모든 $n$ 에서 같아야 한다. $n \log n$ 항은 양쪽이 $a\,n\log n$ 으로 이미 같으니, 나머지를 비교한다.

$$-a\,n + 2c + n = c$$

$n$ 에 비례하는 항과 상수항이 각각 따로 맞아떨어져야 하므로,

• $n$ 의 계수: $-a + 1 = 0 \;\Rightarrow\; a = 1$
• 상수항: $2c = c \;\Rightarrow\; c = 0$

$b$ 는 식 어디에서도 제약을 받지 않는다(기저 조건 $T(1)$ 으로 정해질 뿐이다). 따라서

$$T(n) = n \log n + b\,n = O(n \log n)$$

추측한 모양이 점화식과 모순 없이 들어맞았으므로, merge sort는 입력에 상관없이 $\Theta(n \log n)$ 이다.

---

메모리라는 함정

시간만 보면 merge sort는 흠잡을 데 없다. 시간 분석에 잡히지 않는 비용이 하나 더 있다. 병합할 때마다 결과를 담을 배열 b[n] 을 새로 만든다.

$$\text{추가 메모리} = O(n)$$

앞 절의 시간 분석은 비교와 이동 같은 추상 연산의 횟수만 세었으므로 이 비용은 거기에 잡히지 않는다. 재귀 깊이마다 배열을 새로 잡더라도 한 번에 살아 있는 것은 한 단계분이라 추가 공간의 최댓값은 $O(n)$이다.

실행 시간에도 영향이 있다. 큰 배열을 확보하는 일은 운영체제가 페이지를 잡아 주는 일이라 공짜가 아니고, $n$ 이 커질수록 할당에 드는 시간이 늘어난다. 시간 복잡도가 같은 $O(n \log n)$ 이라도 추가 배열을 쓰지 않는 정렬보다 느려질 수 있다. 이 차이는 $n$ 이 크고 가용 메모리가 빠듯할 때 드러난다.

그래서 추가 배열 없이 $O(n \log n)$ 을 내는 정렬이 필요해진다. 그 답이 heap sort다.

---

Heap Sort — 제자리에서 $O(n \log n)$

heap sort는 배열 안에서 최대 힙(max-heap) 을 만들고 허무는 방식으로, 추가 배열 없이 정렬한다.

1. 배열 전체를 최대 힙으로 만든다. 루트에는 항상 가장 큰 값이 온다.
2. 루트(최댓값)를 배열의 맨 끝 원소와 맞바꾼다. 가장 큰 값이 제자리에 놓인다.
3. 맨 끝 한 칸을 정렬 완료로 떼어 내고, 줄어든 힙을 다시 정렬해(재배열) 새 최댓값을 루트로 올린다.
4. 힙이 빌 때까지 2–3을 반복하면 배열이 오름차순으로 정렬된다.

힙을 한 번 재배열하는 데 $O(\log n)$, 이를 $n$ 번 반복하므로 전체는 $O(n \log n)$ 이다. 결정적인 차이는 모든 작업이 원래 배열 안에서 교환만으로 일어난다는 점이다. 추가 메모리는 $O(1)$ 로, merge sort의 메모리 함정을 피한다.

---

정렬의 하한: 왜 더 빠를 수 없는가

merge sort와 heap sort 모두 $O(n \log n)$ 이다. 자연스러운 질문이 떠오른다. 이보다 빠른 정렬이 가능할까? $O(n)$ 짜리 비교 정렬을 누군가 찾아낼 수 있을까?

놀랍게도 답은 “불가능”이며, 이것은 증명할 수 있다.

비교 모델

먼저 게임의 규칙을 정한다. 비교 모델(comparison model) 에서는 알고리즘이 원소끼리의 비교만 할 수 있다고 본다. 두 원소 $a_i, a_j$ 를 비교하면 결과는 $a_i < a_j$ 또는 $a_i > a_j$ 둘 중 하나다. 비교에 걸리는 시간은 무시하고 비교 횟수만 센다. 선택·병합·quick sort를 비롯한 대부분의 범용 정렬이 이 모델에 들어간다.

결정 트리

어떤 비교 정렬이든, 그 실행은 결정 트리(decision tree) 로 그릴 수 있다. 내부 노드는 하나의 비교, 두 갈래는 그 결과($<$ 인지 $>$ 인지)다. 비교 결과를 따라 내려가다 잎(leaf)에 닿으면, 그곳이 알고리즘이 확정한 하나의 정렬 순서다.

여기서 핵심 관찰이 나온다. 서로 다른 $n$ 개 원소의 가능한 정렬 순서는 $n!$ 가지다. 알고리즘은 이 $n!$ 가지를 모두 구별할 수 있어야 하므로, 결정 트리에는 적어도 $n!$ 개의 잎이 있어야 한다.

높이가 곧 최악 비교 횟수

결정 트리에서 루트부터 잎까지의 경로 길이는 그 입력에서 수행한 비교 횟수다. 따라서 트리의 높이 $h$ 가 곧 최악의 경우 비교 횟수다.

그런데 한 번의 비교는 갈래를 둘로 나누므로, 결정 트리는 이진 트리다. 높이 $h$ 인 이진 트리의 잎은 많아야 $2^h$ 개다. 잎이 $n!$ 개 이상 필요하다고 했으니,

$$2^h \ge n! \quad\Longrightarrow\quad h \ge \log_2 (n!)$$

이제 $\log_2(n!)$ 의 크기만 가늠하면 된다.

$\log_2(n!) = \Theta(n \log n)$

위쪽 한계는 쉽다. $n! = 1 \cdot 2 \cdots n \le n \cdot n \cdots n = n^n$ 이므로,

$$\log_2(n!) \le \log_2(n^n) = n \log_2 n$$

아래쪽 한계는 곱의 뒤쪽 절반만 남겨 얻는다. $n/2$ 보다 큰 항이 $n/2$ 개 있고, 각각은 적어도 $n/2$ 이므로

$$n! \ge \left(\frac{n}{2}\right)^{n/2} \quad\Longrightarrow\quad \log_2(n!) \ge \frac{n}{2}\log_2\frac{n}{2} = \frac{n}{2}\big(\log_2 n - 1\big)$$

두 한계를 합치면 $\log_2(n!)$ 은 위로도 아래로도 $n \log n$ 에 묶인다.

$$\log_2(n!) = \Theta(n \log n)$$

결론

$h \ge \log_2(n!) = \Omega(n \log n)$ 이므로, 어떤 비교 기반 정렬이든 최악의 경우 $\Omega(n \log n)$ 번의 비교가 필요하다. 이 벽은 영리한 구현으로 넘을 수 있는 것이 아니라, 정렬이라는 문제 자체에 박힌 한계다.

그렇다면 merge sort와 heap sort의 $O(n \log n)$ 은 이 하한과 정확히 맞닿는다. 즉 두 알고리즘은 점근적으로 최적(asymptotically optimal) 이다. 비교만으로 정렬하는 한, 이보다 더 빠른 알고리즘은 존재하지 않는다.