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.