# radix sort

(algorithm)

**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 ...)

*distribution sort*.

**See also**
*postman's sort*, *bucket sort*, *American flag sort*, *top-down radix sort*.

*Note:
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

34 44

When the first pass is done, we have the following.

41 11

12 42 32 32

23

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.

11 12

23

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.)

Author: PEB

## Implementation

Explanation and code (Pascal). (C and Pascal). analysis, explanation, and code (C). tutorial with examples and code (C++).

Go to the
Dictionary of Algorithms and Data
Structures home page.

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