기수 정렬

기수 정렬(Radix sort)은 정렬 알고리즘의 하나이다. 기수 정렬은 레코드를 비교하지 않고 정렬을 수행하기 때문에, 비교를 기초한 방법들이 이론적인 하한선인 $O(n\log _{2}n)$을 깰 수 없는 데 반해 $O(dn)$의 시간복잡도를 가진다. 기수 정렬의 단점은 추가적인 메모리를 필요로 한다는 것과 정렬할 수 있는 레코드의 타입이 한정된다는 것이다.

기수 정렬은 가장 낮은 자리수(Least Significant Digit;LSD)부터 혹은 가장 높은 자리수(MSD;Most Significant Digit)부터 할 수 있다. LSD 기수 정렬은 레코드의 안정성을 유지하는 것을 유념하여 낮은 자리수부터 차례로 버킷 정렬하면 된다. MSD 기수 정렬은 레코드를 높은 자리수부터 재귀적으로 정렬한다.