왜 O(n²)을 넘어서야 하는가

06편에서 다룬 선택·삽입·버블 정렬은 모두 평균·최악 시간 복잡도가 $O(n^2)$이었다. 자료가 100개면 최대 비교 횟수가 대략 5,000번 수준이지만, 자료가 100만 개가 되면 5천억 번에 가까운 연산이 필요해져 사실상 쓸 수 없다. 이 한계를 넘는 방법이 15편에서 본격적으로 다룰 분할정복(divide and conquer) 기법이다. 이 편에서 다루는 퀵 정렬과 병합 정렬은 분할정복을 정렬에 적용한 대표 사례이며, 04편에서 배운 재귀 트레이스와 점화식 분석을 실제로 사용하는 첫 사례이기도 하다.

분할정복의 기본 흐름은 세 단계다. (1) 문제를 더 작은 부분 문제로 분할(divide)한다. (2) 각 부분 문제를 재귀적으로 정복(conquer)한다. (3) 부분 문제의 해를 합쳐 원래 문제의 해를 만든다(결합, combine). 퀵 정렬과 병합 정렬은 이 세 단계를 서로 다른 지점에서 수행한다는 점이 핵심 차이다.

병합 정렬: 반으로 쪼개고 순서대로 합친다

쉽게 말하면: 배열을 반씩 계속 쪼개 원소 하나짜리로 만든 다음, 두 개씩 비교하며 정렬된 상태로 다시 합쳐 나간다.

병합 정렬(merge sort)은 배열을 절반으로 나누는 분할은 아주 단순하게 하고, 대신 나뉜 두 부분을 정렬된 상태로 합치는 병합(merge) 단계에서 실제 정렬 작업을 수행한다.

병합 정렬 의사코드

MergeSort(A, left, right)
  if left < right
    mid = (left + right) / 2
    MergeSort(A, left, mid)
    MergeSort(A, mid+1, right)
    Merge(A, left, mid, right)

Merge(A, left, mid, right)
  왼쪽 부분(A[left..mid])과 오른쪽 부분(A[mid+1..right])을
  각각 앞에서부터 하나씩 비교해, 더 작은 값을 임시 배열에 순서대로 담는다.
  다 담은 뒤 임시 배열 내용을 A[left..right]에 다시 복사한다.

배열 [38, 27, 43, 3]의 분할 과정 (재귀 트리)

원소가 하나만 남으면(리프 노드) 그 자체로 이미 정렬된 것이므로 더 이상 쪼개지 않고 병합을 시작한다.

병합 과정 단계별 표

2단계 병합을 자세히 보면, 왼쪽 [27, 38]과 오른쪽 [3, 43]의 맨 앞 값을 계속 비교한다.

결과 해석: 병합 정렬의 핵심은 “이미 각각 정렬된 두 부분을 합칠 때는, 양쪽의 맨 앞만 비교하면 된다”는 사실이다. 한쪽이 먼저 바닥나면 남은 쪽을 그대로 뒤에 이어 붙이면 되므로, 병합 한 번에 걸리는 시간은 두 부분의 원소 수를 합친 만큼, 즉 $O(k)$($k$는 합친 길이)다.

병합 정렬의 복잡도 유도 (점화식)

배열 길이 $n$을 병합 정렬하는 데 걸리는 시간을 $T(n)$이라 하면, 분할은 절반씩 두 개의 부분 문제로 나뉘고(각 부분 문제 크기 $n/2$), 병합에는 $O(n)$이 걸리므로 다음 점화식이 성립한다.

• $2T(n/2)$: 크기 $n/2$인 부분 문제 2개를 재귀적으로 정렬하는 시간
• $O(n)$: 두 정렬된 부분을 병합하는 데 드는 시간

04편에서 배운 마스터 정리를 적용하면, $a=2$, $b=2$, $f(n)=O(n)$이고 $n^{\log_b a} = n^{\log_2 2} = n^1 = n$이므로 $f(n)$과 $n^{\log_b a}$가 같은 차수인 케이스 2에 해당한다. 이 경우 해는 다음과 같다.

이를 재귀 트리로 직접 눈으로도 확인할 수 있다. 트리의 깊이는 $n$을 절반씩 나눠 1이 될 때까지 걸리는 횟수인 $\log_2 n$이고, 각 깊이(레벨)마다 그 레벨의 모든 부분 배열 크기를 합치면 항상 $n$이다(예: 레벨 0은 크기 $n$짜리 1개, 레벨 1은 크기 $n/2$짜리 2개로 합이 $n$, 레벨 2는 크기 $n/4$짜리 4개로 합이 $n$). 레벨마다 병합 비용이 $O(n)$이고 레벨 수가 $\log_2 n$개이므로 전체는 $O(n) \times O(\log n) = O(n \log n)$이다.

• 시간 복잡도: 최선·평균·최악 모두 $O(n \log n)$ (분할이 항상 정확히 절반이라 입력 상태에 영향받지 않는다)
• 공간 복잡도: 병합 과정에서 원본과 같은 크기의 임시 배열이 필요하므로 $O(n)$ → 제자리 정렬이 아니다
• 안정성: Merge에서 왼쪽 값과 오른쪽 값이 같을 때 왼쪽 값을 먼저 선택하도록 구현하면 순서가 유지된다 → 안정 정렬

퀵 정렬: 피벗을 기준으로 나누고, 나눈 뒤에는 그대로 둔다

쉽게 말하면: 기준값(피벗)을 하나 정해서, 그보다 작은 값은 왼쪽으로 큰 값은 오른쪽으로 보낸 다음, 양쪽을 각각 다시 같은 방식으로 정렬한다.

퀵 정렬(quick sort)은 병합 정렬과 반대로, 분할 단계에서 실제 정렬 작업(피벗보다 작은/큰 값 나누기)을 수행하고, 나뉜 두 부분을 재귀적으로 정렬한 뒤에는 다시 합칠 필요가 없다(이미 왼쪽은 전부 오른쪽보다 작은 값들이므로 이어 붙이기만 하면 끝).

퀵 정렬 의사코드 (로무토 파티션)

QuickSort(A, low, high)
  if low < high
    p = Partition(A, low, high)
    QuickSort(A, low, p-1)
    QuickSort(A, p+1, high)

Partition(A, low, high)
  pivot = A[high]
  i = low - 1
  for j = low to high-1
    if A[j] <= pivot
      i = i + 1
      A[i]와 A[j]를 교환
  A[i+1]와 A[high]를 교환
  return i+1

이 의사코드는 배열의 마지막 원소를 피벗으로 삼는 로무토(Lomuto) 파티션 방식이다. i는 “피벗보다 작거나 같은 값들의 마지막 위치”를 가리키는 포인터이고, j는 배열을 훑는 포인터다.

배열 [10, 80, 30, 90, 40]의 파티션 과정 (피벗 40)

결과 해석: 파티션이 끝나면 피벗 40은 정확히 자기 자리(인덱스 2)에 놓이고, 왼쪽 [10, 30]은 모두 40보다 작고 오른쪽 [90, 80]은 모두 40보다 크다. 이제 왼쪽 부분과 오른쪽 부분을 각각 독립적으로 다시 퀵 정렬하면 된다. 함수는 피벗의 최종 위치(인덱스 2)를 반환한다.

퀵 정렬의 복잡도 유도: 피벗 선택이 전부를 좌우한다

퀵 정렬의 성능은 피벗이 배열을 얼마나 균등하게 나누는지에 전적으로 달려 있다.

최선의 경우 — 매번 정확히 절반으로 나뉠 때

이 점화식은 병합 정렬과 완전히 같은 형태이므로 같은 방법(마스터 정리 케이스 2)으로 풀리며 $T(n) = O(n \log n)$이다.

최악의 경우 — 매번 피벗이 최솟값이나 최댓값이라 한쪽에 아무것도 남지 않을 때

이미 정렬된 배열에 “마지막 원소를 피벗으로” 쓰는 로무토 파티션을 적용하면, 매번 피벗이 그 구간의 최댓값이 되어 한쪽 부분 문제의 크기가 0, 다른 쪽은 $n-1$이 된다.

이 점화식을 반복 대입하면 $T(n) = O(n) + O(n-1) + \cdots + O(1) = O(n^2)$이 된다. 재귀 트리로 보면 트리의 깊이가 $\log n$이 아니라 $n$이 되어(매 레벨마다 크기가 1씩만 줄어드므로), 선택 정렬과 같은 수준으로 느려진다.

• 시간 복잡도: 최선·평균 $O(n \log n)$, 최악 $O(n^2)$
• 공간 복잡도: 추가 배열은 쓰지 않지만 재귀 호출 스택이 최선의 경우 $O(\log n)$, 최악의 경우 $O(n)$ 깊이까지 쌓인다 → 정렬 자체는 제자리 정렬로 분류하지만 재귀 스택 공간은 별도로 고려해야 한다.
• 안정성: 파티션 과정에서 피벗과 멀리 떨어진 원소끼리 교환이 일어나 같은 값의 순서가 바뀔 수 있다 → 불안정 정렬

피벗 선택 전략과 함정

시험에서 자주 나오는 함정은 “퀵 정렬은 항상 병합 정렬보다 빠르다”는 명제다. 이는 틀렸다. 퀵 정렬은 평균적으로 병합 정렬보다 실제 상수 계수가 작아 실무에서 더 빠른 경우가 많지만, 피벗이 계속 나쁘게 뽑히는 입력(예: 이미 정렬된 배열에 고정된 피벗 전략을 쓰는 경우)에서는 $O(n^2)$까지 떨어질 수 있어 최악의 경우 성능은 병합 정렬($O(n \log n)$ 보장)보다 나쁘다.

병합 정렬 vs 퀵 정렬 종합 비교

자주 틀리는 점

• 병합 정렬의 공간 복잡도를 $O(1)$로 착각한다. 병합 단계에서 정렬된 결과를 임시로 담을 배열이 필요해 $O(n)$ 추가 공간이 든다. 이는 병합 정렬이 제자리 정렬이 아닌 이유이기도 하다.
• 퀵 정렬의 최악 시간 복잡도를 $O(n \log n)$으로 잘못 외운다. 퀵 정렬의 최악은 피벗이 계속 한쪽으로 치우칠 때 $O(n^2)$이다. 평균은 $O(n \log n)$이지만 최악과 평균을 구분해야 한다.
• 점화식 $T(n) = 2T(n/2) + O(n)$과 $T(n) = T(n-1) + O(n)$을 같은 결과로 착각한다. 전자는 마스터 정리 케이스 2로 $O(n \log n)$, 후자는 등차수열 합으로 $O(n^2)$이 되어 결과가 완전히 다르다. 재귀 트리의 “깊이”가 $\log n$인지 $n$인지가 이 차이를 만든다.
• 퀵 정렬을 무조건 불안정 정렬이라 외우면서 병합 정렬도 불안정이라고 헷갈린다. 병합 정렬은 병합 시 왼쪽을 먼저 선택하도록 구현하면 안정 정렬이 된다. 안정성은 퀵 정렬만의 문제다.
• “이미 정렬된 배열이니 퀵 정렬이 빠를 것”이라 가정한다. 고정된 피벗 전략(첫 원소·마지막 원소)에서는 이미 정렬된 배열이 오히려 최악의 입력이 된다.

핵심 정리

• 병합 정렬은 분할을 단순하게 하고 병합에서 정렬하며, 점화식 $T(n)=2T(n/2)+O(n)$에서 항상 $O(n \log n)$이 보장되지만 $O(n)$ 추가 공간이 필요하고 안정 정렬이다.
• 퀵 정렬은 파티션에서 정렬하고 결합이 필요 없으며, 평균 $O(n \log n)$이지만 피벗이 나쁘면 최악 $O(n^2)$까지 떨어지고, 불안정 정렬이다.
• 재귀 트리의 깊이(레벨 수)와 레벨당 작업량을 곱하는 방식으로 점화식의 해를 직관적으로 검산할 수 있다.
• 피벗 선택 전략(고정 vs 무작위 vs 중앙값)이 퀵 정렬의 최악 케이스 발생 가능성을 좌우한다.
• 다음 08편에서는 힙 자료구조를 이용해 $O(n \log n)$을 보장하면서도 추가 공간이 거의 필요 없는 힙 정렬을 다룬다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제  — 4단계 알고리즘 과목 출제범위 중 분할정복 정렬 항목 확인
• GeeksforGeeks: QuickSort  — 로무토 파티션 의사코드와 최선·평균·최악 복잡도 분석 참고
• GeeksforGeeks: Merge Sort  — 병합 정렬의 분할·병합 과정과 복잡도 유도 참고