A Radix sort is a fast stable sorting algorithm which can be used to sort items that are identified by unique keys Every key is a string or number
and radix sort sorts these keys in some particular lexicographic-like order The algorithm operates in time where n is the number of items
and k is the average key length This algorithm was originally used to sort punched cards in several passes A computer algorithm was invented
for radix sort at MIT by Harold Seward In many newer applications requiring super speeds and massive memory
the computer radix sort is an improvement on slower comparison sorts Radix sort has resurfaced as an alternative to other
high performance sorting algorithms like heapsort and mergesort which require comparisons where n is the number of items to be sorted
These other algorithms are able to sort with respect to more complicated orderings than a lexicographic one but this is of little
importance in many practical applications A radix sort algorithm works as follows take the least significant digit or group of bits
both being examples of radices of each key sort the list of elements based on that digit but keep the order of elements with
the same digit this is the definition of a stable sort repeat the sort with each more significant digit
The sort in step is usually done using bucket sort which works since there are only finitely many digits
If the size of the possible key space is proportional to the number of items then each key will be symbols long and radix sort uses
time in this case In practice time is only observed when the number of items is much greater than the size of the key space
If the keys used are short integers it is practical to complete the sorting with only two passes and comparisons can be done
with only a few bit operations that operate in constant time In this case and even when sorting bit floating point numbers
radix sort can in practice be significantly faster than any other sorting algorithm
The greatest disadvantages of radix sort are that it usually cannot be made to run in place so additional memory space is needed
and that it requires one pass over the input list for each symbol in the key so it is very slow for potentially long keys Multiple
histogramming techniques where all the required histograms are constructed in a single pass can reduce the latter problem
Radix sort typically uses the following sorting order short keys come before longer keys and keys of the same length are sorted lexicographically
This coincides with the normal order of numbers if the numbers are represented as digit strings