Merge Sort
항상 O(n log n)이고 stable입니다. 단, 병합용 O(n) 보조 배열이나 linked list 병합 비용을 고려합니다.
정렬 선택
병합·퀵·힙 정렬 트레이드오프
비교 정렬은 평균 시간만 보지 않습니다. 안정성, 추가 메모리, 피벗 편향, 최악 O(n log n) 보장, 재귀 깊이를 입력 특성과 함께 봅니다.
입력 제약별 선택
O(n log n)Quick Sort
평균 O(n log n)이고 연속 구간을 제자리에서 훑어 캐시 미스가 적습니다. 이미 정렬된 입력에서 나쁜 피벗이면 O(n²)와 깊은 재귀가 납니다.
Heap Sort
추가 메모리 O(1)과 최악 O(n log n)을 보장하지만 stable이 아니고 지역성이 퀵 정렬보다 나쁠 수 있습니다.
Stable
여러 키를 순서대로 정렬하거나 원래 순서가 의미 있으면 안정 정렬이 필요합니다.
Memory
메모리 제한이 엄격하면 병합 정렬은 부담입니다. 대신 힙 정렬이나 introsort 계열을 봅니다.
Worst Case
랜덤 피벗, median-of-three, introsort 전환이 없으면 공격적 입력에서 시간 초과가 납니다.
안정성메모리최악 시간정렬 선택
표준 라이브러리 정렬은 보통 하이브리드 전략을 씁니다. 직접 구현할 때는 안정성, 보조 메모리, 피벗 방어, 재귀 한계를 먼저 명시합니다.