tradeoff map

같은 O(N log N)이라도 포기하는 비용이 다르다

시간 복잡도가 같아도 안정성, 메모리, 최악 시간 보장이 다르다.

정렬얻는 것포기하는 것선택 신호
Merge안정성, 예측 가능한 시간추가 배열 O(N)stable이 중요할 때
Quick평균 빠름, locality 좋음나쁜 pivot이면 최악 O(N²)일반 배열 정렬
Heap추가 메모리 작음, 최악 보장cache locality와 안정성 약함메모리 제한이 강할 때
핵심: “빠른 정렬”이 아니라 안정성, 메모리, 최악 시간 중 무엇을 포기할지 고르는 문제다.