정렬은 평균 시간보다 입력 성격을 먼저 본다
같은 O(n log n)이어도 안정성, 최악 시간, 추가 공간, 키 형태에 따라 선택이 달라진다.
단순하지만 큰 무작위 입력은 피한다.
피벗 편향이면 최악 O(n²) 가능
같은 키 순서를 보존하지만 공간 필요
| 구분 | 의미 | 판단 |
|---|---|---|
| 최악 보장 | 힙 정렬 | O(n log n), 안정 정렬 아님 |
| 자릿수 키 | 기수 정렬 | 정수·문자열 조건과 버킷 공간 필요 |
| 읽는 순서 | 입력 모양 → 보장 조건 → 부가 조건 | 마지막에 이름 확정 |
핵심 같은 O(n log n)이어도 안정성, 최악 시간, 추가 공간, 키 형태에 따라 선택이 달라진다.