A Fast Radix Sort

Almost all computers regularly sort data. Many different sort algorithms have therefore been proposed, and the properties of thses algorithms studied in great detail. It is known that no sort algorithm based on key comparisons can sort N keys in less than O(NlogN) operations, and that many perform O(n 2 ) operations in the worst case. The radix sort has the attractive feature that it can sort N keys in O(N) operations, ant it is therefore natural to consider methods of implementing such a sort efficiently. In this paper one efficient implementation of a radix sort is presented, and the performance of this algorithm compared with that of Quicksort