기수 정렬은 키를 자릿수나 비트 묶음으로 나누고 각 부분을 처리하여 전체 순서를 만드는 방법이다.
원리
낮은 자리부터 처리하는 LSD 방식은 각 단계의 안정성이 중요하다. 자릿수 d와 한 자리의 범위 k를 쓰는 구현은 대략 O(d(n+k)) 비용으로 분석한다.
예시
세 자리 양의 정수를 일의 자리, 십의 자리, 백의 자리 순서로 안정 정렬하면 앞서 정리한 낮은 자리의 순서가 보존된다.
주의할 점
음수, 가변 길이 문자열과 부동소수점은 표현 규칙에 맞는 처리가 필요하다. 숫자 비교 순서와 원시 바이트의 사전식 순서를 동일하게 가정하지 않는다.