MERGE · HEAP
분할정복 짝꿍과 힙 활용 — 모두 평균 O(n log n)
병합 정렬 (Merge)O(n log n)
반으로 계속 쪼개 길이 1까지 → 두 줄 합치며 정렬. 최악도 보장 · 안정 정렬 · 추가 메모리 O(n).
힙 정렬 (Heap)O(n log n)
최대 힙 구성 → 루트(최댓값)를 꺼내 뒤로 → 힙 재구성 반복. 최악도 보장 · 제자리(in-place).
합격 공식
퀵 · 병합 · 힙 — 고급 3총사는 모두 평균 O(n log n)
함정 차단
퀵만 최악 O(n²), 병합·힙은 최악도 O(n log n) 보장. 이 차이가 단골 함정.