고급 정렬 도입 기준

고급 정렬은 요구 조건을 확정한 뒤 선택한다

병합, 퀵, 힙 정렬의 차이는 평균 속도보다 안정성, 메모리, 최악 시간 보장, 피벗 위험에서 분명해집니다.

병합

동일 키 순서: 결과 품질

로그나 주문처럼 원래 순서를 보존해야 하면 보조 메모리 비용을 감수하고 안정 정렬을 우선합니다.

퀵

평균 성능과 피벗 전략 검토

중복 다량, 이미 정렬된 입력, 편향 피벗에서 분할 균형이 무너지는지 별도 반례로 확인합니다.

힙

최악 시간 보장이 우선인 선택

캐시 효율은 불리할 수 있지만 `O(N log N)` 경계를 안정적으로 유지해야 할 때 후보가 됩니다.

안정성 같은 키의 원래 순서를 테스트 데이터로 남깁니다.
메모리 보조 배열 허용량을 입력 최대치와 함께 계산합니다.
최악 역순, 정렬 완료, 중복 다량을 분리해 측정합니다.
벤치 파싱과 복사 비용을 정렬 시간에 섞으면 판단이 왜곡됩니다.