In computer science, radix sort is a non-comparative sorting algorithm. It avoids comparison by creating and distributing elements into buckets according to their radix. For elements with more than one significant digit, this bucketing process is repeated for each digit, while preserving the ordering of the prior step, until all digits have been considered. For this reason, radix sort has also been called bucket sort and digital sort. Radix sort can be applied to data that can be sorted lexicographically, be they integers, words, punch cards, playing cards, or the mail.
History Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines. Radix sorting algorithms came into common use as a way to sort punched cards as early as 1923. The first memory-efficient computer algorithm for this sorting method was developed in 1954 at MIT by Harold H. Seward. Computerized radix sorts had previously been dismissed as impractical because of the perceived need for variable allocation of buckets of unknown size. Seward's innovation was to use a linear scan to determine the required bucket sizes and offsets beforehand, allowing for a single static allocation of auxiliary memory. The linear scan is closely related to Seward's other algorithm — counting sort. In the modern era, radix sorts are most commonly applied to collections of binary strings and integers. It has been shown in some benchmarks to be faster than other more general-purpose sorting algorithms, sometimes 50% to three times faster.
Digit order Radix sorts can be implemented to start at either the most significant digit (MSD) or least significant digit (LSD). For example, with 1234, one could start with 1 (MSD) or 4 (LSD). LSD radix sorts typically use the following sorting order: short keys come before longer keys, and then keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, like the sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]. LSD sorts are generally stable sorts. MSD radix sorts are most suitable for sorting strings or fixed-length integer representations. A sequence like [b, c, e, d, f, g, ba] would be sorted as [b, ba, c, d, e, f, g]. If lexicographic ordering is used to sort variable-length integers in base 10, then numbers from 1 to 10 would be output as [1, 10, 2, 3, 4, 5, 6, 7, 8, 9], as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key. MSD sorts are not necessarily stable. Other than the traversal order, MSD and LSD sorts differ in their handling of variable length input. LSD sorts can group by length, radix sort each group, then concatenate the groups in size order. MSD sorts must effectively 'extend' all shorter keys to the size of the largest key and sort them accordingly, which can be more complicated than the grouping required by LSD. However, MSD sorts are more amenable to subdivision and recursion. Each bucket created by an MSD step can itself be radix sorted using the next most significant digit, without reference to any other buckets created in the previous step. Once the last digit is reached, concatenating the buckets is all that is required to complete the sort.
Examples
Least significant digit Input list:
[170, 45, 75, 90, 2, 802, 2, 66] Starting from the rightmost (last) digit, sort the numbers based on that digit:
[{170, 90}, {2, 802, 2}, {45, 75}, {66}] Sorting by the next left digit:
[{02, 802, 02}, {45}, {66}, {170, 75}, {90}] Notice that an implicit digit 0 is prepended for the two 2s so that 802 maintains its position between them. And finally by the leftmost digit:
[{002, 002, 045, 066, 075, 090}, {170}, {802}] Notice that a 0 is prepended to all of the 1- or 2-digit numbers. Each step requires just a single pass over the data, since each item can be placed in its bucket without comparison with any other element. Some radix sort implementations allocate space for buckets by first counting the number of keys that belong in each bucket before moving keys into those buckets. The number of times that each digit occurs is stored in an array. Although it is always possible to pre-determine the bucket boundaries using counts, some implementations opt to use dynamic memory allocation instead.
Most significant digit, forward recursive Input list, fixed width numeric strings with leading zeros:
[170, 045, 075, 025, 002, 024, 802, 066] First digit, with brackets indicating buckets:
[{045, 075, 025, 002, 024, 066}, {170}, {802}] Notice that 170 and 802 are already complete because they are all that remain in their buckets, so no further recursion is needed Next digit:
[{ {002}, {025, 024}, {045}, {066}, {075} }, 170, 802] Final digit:
[ 002, { {024}, {025} }, 045, 066, 075 , 170, 802] All that remains is concatenation:
[002, 024, 025, 045, 066, 075, 170, 802]
… excerpt ends here. Continue reading the full article.
