비교 정렬 — 퀵·머지·힙, 그리고 Ω(n log n)이라는 넘을 수 없는 벽
퀵·머지·힙 정렬의 원리와 트레이드오프, 비교 정렬의 하한 Ω(n log n), 그리고 안정 정렬이 왜 중요한지. 막대가 자리를 바꾸는 애니메이션으로 정리합니다.
정렬은 “비교”만으로 얼마나 빨라질 수 있나
정렬은 거의 모든 시스템의 바닥에 깔려 있습니다. DB 인덱스 빌드, GROUP BY, 검색 결과 랭킹, 중복 제거 — 모두 정렬을 깔고 시작합니다. 그런데 두 원소의 대소만 비교할 수 있을 때(a < b?), 정렬은 아무리 영리해도 Ω(n log n)보다 빠를 수 없습니다. 이 글은 그 벽이 왜 존재하는지, 그리고 그 벽에 가장 가까이 붙은 세 알고리즘 — 퀵·머지·힙 — 이 각각 무엇을 사고 무엇을 파는지를 다룹니다.
막대로 보는 정렬 — 자리를 바꾸며 질서가 생긴다
먼저 감을 잡읍시다. 아래는 뒤섞인 막대들이 비교·교환을 거쳐 키 순으로 자리를 잡는 과정입니다. 모든 비교 정렬이 결국 하는 일은 이것 — “잘못 놓인 쌍(inversion)”을 줄여 나가는 것입니다.
퀵 정렬 — 평균은 왕, 최악은 함정
| 퀵 정렬은 피벗(pivot)을 하나 골라, 배열을 “피벗보다 작은 것 | 피벗 | 큰 것”으로 분할(partition) 한 뒤 좌우를 재귀적으로 정렬합니다. 분할 정복의 대표 사례죠. |
1
2
3
4
5
def quicksort(a, lo, hi):
if lo >= hi: return
p = partition(a, lo, hi) # 피벗 자리 확정, O(hi-lo)
quicksort(a, lo, p - 1)
quicksort(a, p + 1, hi)
아래는 피벗(빨강)을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 모이는 파티션 과정입니다.
평균 $\Theta(n \log n)$로 상수가 작아 실측이 가장 빠른 편입니다(메모리 지역성이 좋고, 추가 공간이 거의 없음). 그러나 이미 정렬된 입력 + 끝 원소 피벗 같은 조합에선 분할이 1:n-1로 치우쳐 최악 $O(n^2)$. 실무 라이브러리는 이걸 막으려 랜덤/median-of-three 피벗을 쓰고, 재귀가 깊어지면 힙 정렬로 전환하는 introsort(C++ std::sort)를 씁니다. 작은 구간은 삽입 정렬로 마무리합니다.
악의적 입력으로 일부러 최악 $O(n^2)$를 유도하는 게 복잡도 공격의 한 형태입니다. “평균만 보면 된다”가 안 통하는 이유.
머지 정렬 — 안정적이고 예측 가능한 일꾼
머지 정렬은 절반으로 나눠 각각 정렬한 뒤, 두 정렬된 배열을 병합(merge) 합니다. 분할은 공짜, 일은 병합에서 일어납니다.
flowchart TD
A["[5,2,8,1]"] --> B["[5,2]"] & C["[8,1]"]
B --> B1["[5]"] & B2["[2]"]
C --> C1["[8]"] & C2["[1]"]
B1 & B2 --> M1["merge → [2,5]"]
C1 & C2 --> M2["merge → [1,8]"]
M1 & M2 --> R["merge → [1,2,5,8]"]
핵심 성질:
- 최악도 $\Theta(n\log n)$ 보장 — 입력이 어떻든 흔들리지 않음. p99 지연이 중요한 곳에서 강점.
- 안정 정렬(stable) — 같은 키의 상대 순서를 보존(아래에서 설명).
- 대신 $O(n)$ 추가 공간이 필요. 이 “병합” 구조가 메모리에 다 안 들어가는 데이터를 디스크에서 정렬하는 외부 정렬의 뼈대가 됩니다.
힙 정렬 — 추가 공간 없는 보장된 n log n
힙(우선순위 큐)을 만든 뒤 최댓값을 하나씩 뽑아 뒤에서부터 채웁니다. 제자리(in-place) + 최악 $O(n\log n)$ 보장이라는 두 마리 토끼를 잡지만, 캐시 지역성이 나빠(힙은 부모-자식이 메모리상 멀리 떨어짐) 실측은 퀵보다 느린 편입니다. 그래서 보통은 단독으로 쓰기보다 introsort의 안전망으로 쓰입니다.
| 퀵 정렬 | 머지 정렬 | 힙 정렬 | |
|---|---|---|---|
| 평균 | Θ(n log n) | Θ(n log n) | Θ(n log n) |
| 최악 | O(n²) | Θ(n log n) | Θ(n log n) |
| 추가 공간 | O(log n) | O(n) | O(1) |
| 안정성 | 불안정 | 안정 | 불안정 |
| 실측 속도 | 최상(상수 작음) | 중 | 중하(캐시 나쁨) |
안정성(stable) — 같은 점수면 누가 앞에?
안정 정렬은 키가 같은 두 원소의 원래 순서를 보존합니다. “결제액으로 정렬했다가, 다시 등급으로 정렬”하는 다중 키 정렬에서 결정적입니다 — 2차 정렬이 1차 정렬 결과를 흩뜨리지 않아야 하니까요.
퀵·힙은 불안정, 머지는 안정입니다. Java의 Arrays.sort는 객체엔 안정 정렬(TimSort), 기본형엔 불안정(듀얼피벗 퀵) 을 쓰는데, 기본형은 “같은 값”의 구분이 의미 없으니 빠른 쪽을 택한 설계입니다.
Ω(n log n) — 비교만으로는 넘을 수 없는 벽
왜 비교 정렬은 더 빨라질 수 없을까요? 결정 트리(decision tree) 로 직관할 수 있습니다. n개 원소의 가능한 순열은 $n!$가지. 비교 한 번은 “예/아니오” 분기 하나라, 트리의 한 단계입니다. $n!$개의 잎(정답)을 구분하려면 트리 높이가 최소 $\log_2(n!)$ 이어야 하고,
(스털링 근사). 즉 최악의 경우 비교 횟수는 Ω(n log n)을 피할 수 없습니다. 이 벽을 넘으려면 비교를 버리고 키의 구조(자릿수·범위)를 직접 써야 하는데, 그게 다음 글 계수·기수 정렬입니다.
flowchart TD
R{"a<b?"} -->|예| L{"b<c?"} -->|예| O1["abc"]
L -->|아니오| O2["a c b ..."]
R -->|아니오| RR{"a<c?"} --> O3["...순열 n!개의 잎"]
프로덕션 함정
| 함정 | 증상 | 해법 |
|---|---|---|
| 퀵 정렬 최악 O(n²) | 정렬된/적대적 입력에 멈춤 | 랜덤·median-of-three 피벗, introsort |
| 깊은 재귀 스택 오버플로 | 큐가 한쪽으로 치우쳐 재귀 깊이 n | 작은 쪽 먼저 재귀 + 큰 쪽 꼬리 반복 |
| 비교자 비일관성 | “Comparison contract violated” 예외 | 추이律 지키는 comparator(a<b, b<c ⇒ a<c) |
| 안정성 오인 | 다중 키 정렬 결과가 뒤섞임 | 안정 정렬 사용 또는 복합 키 한 번에 비교 |
| 대용량 메모리 초과 | 머지의 O(n) 버퍼로 OOM | 외부 정렬(디스크 k-way merge) |
면접/리뷰 단골 질문
- Q. 퀵이 평균 가장 빠른데 왜 최악이 위험한가? → 분할이 1:n-1로 치우치면 O(n²). 랜덤 피벗·introsort로 방어. 보장이 필요하면 머지/힙.
- Q. 머지를 언제 쓰나? → 최악도 n log n 보장 + 안정성 필요 + 외부 정렬. 대신 O(n) 공간.
- Q. 비교 정렬 하한이 Ω(n log n)인 이유? → 결정 트리. n!개 순열을 구분하려면 높이 ≥ log₂(n!) = Θ(n log n).
- Q. 안정 정렬이 중요한 사례? → 다중 키 정렬(등급→결제액). 2차 정렬이 1차 순서를 보존해야 함.
- Q. Java Arrays.sort가 타입마다 다른 이유? → 객체는 안정 TimSort, 기본형은 빠른 듀얼피벗 퀵(같은 값 구분이 무의미).
정리
- 비교 정렬은 퀵(평균 최강·최악 위험)·머지(보장·안정·O(n)공간)·힙(제자리·보장·캐시 약점) 의 트레이드오프 게임.
- 실무는 이를 섞는다 — introsort(퀵+힙+삽입), TimSort(머지+삽입, 안정).
- 안정성은 다중 키 정렬에서 결정적. Ω(n log n) 은 비교만으로는 못 넘는 정보이론적 벽.
복잡도 분석에서 시작한 시리즈가 이제 정렬에 닿았습니다. 다음 글 선형 시간 정렬에서 이 Ω(n log n) 벽을 “비교를 버리고” 우회하는 법을 봅니다.
</content>