The radix sort is not a

comparison sort. It works in a very similar manner to the punch card sorting equipment used. To get a rough idea of how it works, consider the folowing example.

Suppose we have a set of 3-digit numerical keys, where each 3-digit key is punched on a separate card in a deck of cards. The deck of cards to be sorted is placed in a bin on the sorting machine, and cards to be sorted are fed from the *bottom* of the deck. The machine can be set to sort based on either the first, the middle, or the last digit of the key. Suppose C is the card on the bottom of the deck that is currently being read by the sorting machine. If the digit currently selected in C is a 0, then C is fed mechanically to a bin where it drops down on top of the pile of cards containing 0's digits. If C's currently selected digit is d (which is 0 through 9), it drops on top of the respective digit-d-pile.

After the entire deck has been processed, the piles of cards in the digit bins are stacked to reconstitute a new deck, with the 9's pile of the bottom, the 8's pile next to the bottom, and so on. This deck is fed through the sorting machine another time, with a *different digit* selected for sorting. In this manner, the entire pile can be sorted in 3 tries. For a key with N digits, therefore, it takes N passes to sort the algorithm.

Back to Sorting Algorithms.