Definition: A multiple pass distribution sort algorithm that distributes each item to a bucket according to part of the item's key beginning with the least significant part of the key. After each pass, items are collected from the buckets, keeping the items in order, then redistributed according to the next most significant part of the key.
Generalization (I am a kind of ...)
See also postman's sort, bucket sort, American flag sort, top-down radix sort.
Here is a simple example of the sort. Suppose the input keys are 34, 12, 42, 32, 44, 41, 34, 11, 32, and 23. Four buckets are appropriate, since there are four different digits. The first pass distributes the keys into buckets by the least significant digit. Half way through the first pass, the buckets contain the following, where each line is a bucket.
12 42 32
When the first pass is done, we have the following.
12 42 32 32
34 44 34
We collect these, keeping their relative order: 41 11 12 42 32 32 23 34 44 34. Now we distribute by the next most significant digit, which is the highest digit, and we get the following.
32 32 34 34
41 42 44
When we collect them, they are in order: 11 12 23 32 32 34 34 41 42 44.
[CLR90, page 179] gives an in-place variant of radix sort which uses a stable sort on each digit of the key.
Radix sort can be particularly effective on a linked list. Rather than buckets, put items in linked lists. At the end of a pass collect the items by "sewing" the lists together: make the tail of each list point to the head of the next list. (After Steven Pigeon, QuickSort and Radix Sorts on Lists, Dr. Dobb's Journal, May 2002, pages 89-94.)
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 16 November 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "radix sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 16 November 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/radixsort.html