무엇을 비교하는지 먼저 정하기
학생 기록을 점수로 정렬할 때 점수가 같으면 이름으로 비교할지 기존 순서를 유지할지 정해야 한다. 날짜나 문자열을 정렬할 때도 표현 문자열과 실제 의미의 순서가 다를 수 있다.
비교 함수가 모순된 결과를 내면 정렬 결과를 신뢰하기 어렵다. 일부 값의 비교가 정의되지 않거나 누락된 값이 있으면 그 처리 규칙도 함께 명시해야 한다.
평균과 최악의 경우
알고리즘의 성능은 입력 크기뿐 아니라 데이터의 배치에 영향을 받을 수 있다. 퀵 정렬은 분할 방식에 따라 효율적이지만 편향된 분할이 반복되면 최악의 경우가 나빠질 수 있다. 병합 정렬은 추가 공간을 쓰는 일반적인 구현에서 일관된 시간 복잡도를 제공한다.
비교 기반 정렬의 하한을 모든 정렬 방식에 그대로 적용해서는 안 된다. 키의 범위나 자릿수 같은 추가 구조를 이용하는 계수 정렬과 기수 정렬은 다른 가정 아래 분석한다.
안정 정렬이 필요한 상황
키가 같은 항목들의 기존 상대 순서를 유지하면 안정 정렬이라고 한다. 날짜순 기록을 부서별로 다시 묶으면서 같은 부서 안의 날짜순을 유지하고 싶을 때 이런 성질이 유용하다.
안정성은 결과가 정확하다는 말의 다른 표현이 아니다. 불안정 정렬도 키 순서에 따른 정렬은 올바르게 수행할 수 있다. 어떤 추가 순서가 보존되어야 하는지에 관한 성질이다.
메모리와 실제 환경
추가 메모리를 얼마나 쓰는지, 자료를 연속해서 읽는지, 저장 장치 접근이 얼마나 필요한지도 중요하다. 메모리에 들어오지 않는 대형 자료는 외부 저장 장치를 이용하는 정렬 전략이 필요할 수 있다.
실제 라이브러리는 작은 구간과 큰 구간, 이미 정렬된 구간을 다르게 처리하는 혼합 전략을 쓰기도 한다. 알고리즘 이름 하나보다 입력 조건과 구현의 보장 사항을 확인하는 편이 정확하다.