Assume that we have n integers in the range (0,n2) to be sorted. (For a bin sort, m = n2, and we would have an O(n+m) = O(n2) algorithm.) Sort them in two phases:
As an example, consider the list of integers:
36 9 0 25 1 49 64 16 81 4n is 10 and the numbers all lie in (0..99). After the first phase, we will have:
0 | 1 81 | 64 4 | 25 | 36 16 | 9 49 |
Repeating the process, will produce:
0 1 | 16 | 25 | 36 | 49 | 64 | 81 |
In this second phase, we used the leading decimal digit to allocate items to bins, being careful to add each item to the end of the bin.
We can apply this process to numbers of any size expressed to any suitable base or radix.
typedef struct t_date { int day; int month; int year; } date;If the ranges for day and month are limited in the obvious way, and the range for year is suitably constrained, eg 1900 < year <= 2000, then we can apply the same procedure except that we'll employ a different number of bins in each phase. In all cases, we'll sort first on the least significant "digit" (where "digit" means a field with a limited range), then on the next significant "digit", placing each item after all the items already in the bin, and so on.
Assume that the key of the item to be sorted has k fields, fi|i=0..k-1, and that each fi has si discrete values, then a generalised radix sort procedure might look like this:
radixsort( A, n ) for(i=0;i<k;i++) for(j=0;j<si;j++) bin[j] = EMPTY; for(j=0;j<n;j++) move Ai to the end of bin[Ai->fi] for(j=0;j<si;j++) concatenate bin[j] onto the end of A; |
O(si) O(si) O(si) |
Total |
Now if, for example, the keys are integers in (0..nk-1), for some constant k, then the keys can be viewed as k-digit base-n integers. Thus, si = n| for all i and the time complexity becomes O(n + kn) or O(n). Note that this result depends on k being constant.
It takes logn binary digits to represent an integer <=n,
so that if the key length were allowed to increase with n,
so that k = logn,
then:
.