Beyond Comparisons: Radix Sort and Counting Sort

Other sorting algorithms in these pages use binary comparisons (<, >, ≤, ≥) to control the algorithms. As a result, there is a theoretical lower bound on the number of comparisons (and thus overall operations) needed to sort N items: Ω(N lg N). By exploiting more properties of the data being sorted than its ordering relation, we can arrive at different bounds. Radix sorting uses the digits or bytes constituting the data to make multi-way decisions, and is able to sort B bytes of data in O(B) time. Comparing this result to O(N lg N) comparisons to sort N (multi-byte) records is a bit tricky, but if we assume that in the worst case, comparisons take time proportional to the number of bytes of data being compared, it would seem that radix sorting should win out. As usual, though, for practical purposes we must consider constant factors.

The idea behind radix sorting is that we view the keys to be sorted sequences of numerals consisting of digits in some finite radix (call it R). For example, ASCII character strings can be thought of as base-256 numerals. In effect, we pad all the keys to the same number of digits (on the left or right, depending on sorting order: right for strings, left for numbers). If the common length of the keys is now D digits, we sort the keys (up to) D times, once on their first digit, once on their second, and so forth. The precise logistics differ depending on whether one processes the digits from left to right (MSD radix sort, for Most Significant Digit first), or, as in the old card-based sorters, right to left (LSD radix sort).

For MSD radix sort, each sort rearranges the data into sections that can then be sorted independently—the sections will already be ordered correctly with respect to each other (all words that start with "A" come before all words that start with "B"). We then further refine sections having more than one key by the later character positions until all sections contain just one item.

For LSD radix sort, we sort all the data together on each pass, being careful to maintain the previously established order for keys with the same digit in the position currently being sorted.

We can accomplish each of the one-character sorts in O(N+R) time using a stable counting sort. We first counts the number of keys containing each of the possible digits (0 to R-1) at the current character position (call this position k). From this, it is easy to compute the number of keys whose kthd, and thus the number of keys to the left of those whose kth is d. This in turn allows another pass through the keys, moving them to their proper positions.

The demo below uses integers as keys (radix 10). You can run either LSD or MSD sort. The "Counts" array is used to count the number of keys with a given character at the current character position. The "Positions" array then keeps track of the number of items to the left of a key with a given character at the current character position. When we move a key to its proper position, we also increment the appropriate position count, so that keys with the same character in the current position go to the right of those already moved.

Fast Slow
Input size:
Initial array: Array: Counts: Positions: Character position: # input characters examined: