정렬 선택은 몇 가지 속성으로 귀결됩니다. 시간 복잡도, 안정성, 제자리 메모리 사용, 그리고 데이터의 성격입니다. 모든 곳에서 이기는 단일 정렬은 없습니다.
핵심 속성
- 안정(Stable): 같은 원소가 원래의 상대 순서를 유지합니다(다중 키 정렬에 필요).
- 제자리(In-place): O(1) 또는 O(log n) 추가 메모리를 사용합니다.
- 적응적(Adaptive): 거의 정렬된 입력에서 더 빠릅니다.
| 알고리즘 | 평균 시간 | 최악 | 안정 | 제자리 |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | 예 | 예 |
| Merge | O(n log n) | O(n log n) | 예 | 아니오 |
| Quick | O(n log n) | O(n²) | 아니오 | 예 |
| Heap | O(n log n) | O(n log n) | 아니오 | 예 |
# 대부분의 언어는 튜닝된 하이브리드를 제공합니다. 프로덕션에서는 그것을 선호하세요
sorted(data, key=lambda x: x.priority) # Python의 안정 Timsort
특별한 이유가 없다면 정렬을 직접 구현하지 마세요 — 라이브러리 정렬(Timsort, introsort)은 검증된 하이브리드입니다.
정렬을 데이터와 요구 사항에 맞추면 시간 낭비와 미묘한 버그(안정성 상실 같은) 둘 다를 피할 수 있습니다.
트레이드오프를 이해하면 표준 라이브러리가 왜 Timsort나 introsort 같은 하이브리드를 선택했는지 설명됩니다.
하나의 알고리즘을 암기하는 것이 아니라 이 비교 판단이야말로 실제 엔지니어링과 면접이 보상하는 것입니다.