요구 조건 분류
안정성이 필요한지, 메모리 제한이 작은지, 이미 정렬된 입력이 많은지 먼저 본다.
비교 함수 검증
a < b와 b < a가 동시에 참이 되거나 동률 처리가 흔들리면 정렬 결과를 믿을 수 없다.
최악 입력을 넣는다
퀵 정렬은 pivot 선택이 나쁘면 O(n^2)가 될 수 있으므로 랜덤화나 introsort를 고려한다.
Merge sort
안정성과 예측성
항상 O(n log n)이지만 추가 메모리가 필요하다.
linked list와도 잘 맞는다.
Quick sort
평균 성능
캐시 친화적이고 빠르지만 pivot 선택이 중요하다.
최악 입력 방어가 필요하다.
Heap sort
추가 메모리 적음
O(1) 추가 공간으로 정렬 가능하지만 실제 상수와 cache가 불리할
수 있다.
priority queue 개념과 연결된다.
std::sort
실전 기본값
대개 introsort 계열로 최악을 방어한다.
안정성이 필요하면 stable_sort를 쓴다.
안정성 · 비교자 · 메모리 점검
비교자 원칙
std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return std::tie(a.score, a.id) < std::tie(b.score, b.id);
overflow-wrap: break-word;
word-break: keep-all;
});