Once upon a time, computer programs were written in Fortran* and entered on punched cards, about 2000 cards to a tray. Fortran code was typed in columns 1 to 72 of each card, but columns 73-80 could be used for a card number. If you ever dropped a large deck of cards you were really in the poo, unless the cards had been numbered in columns 73-80. If they had been numbered you were saved+: They could be fed into a card sorting machine and restored to their original order.
The card sorting machine was the size of three or four large filing cabinets. It had a card input hopper and ten output bins, numbered 0 to 9. It read each card and placed it in a bin according to the digit in a particular column, e.g. column 80. This gave ten stacks of cards, one stack in each bin. The ten stacks were removed and concatenated, in order: stack 0, then 1, 2, and so on up to stack 9. The whole process was then repeated on column 79, and again on column 78, 77, etc., down to column 73, at which time your deck was back in its original order!
Note that the cards are sorted on the least significant digit (column 80) first and on the most significant digit (column 73) last. Think about it!
The card sorting machine was a physical realisation of the radix sort algorithm.
It was common practice to number cards in steps of 10 or 100
so that a few new cards could be inserted if necessary.
Cards became bent and worn with repeated use
so there were also card duplicating (and renumbering) machines.
Change the data in the HTML FORM below, click `go', and experiment. The contents of the array after each pass, sorting on a given digit position, are displayed in the trace window:
Each pass through the array takes O(n) time. If the maximum magnitude of a number in the array is `v', and we are treating entries as base `b' numbers, then 1+floor(logb(v)) passes are needed.
If `v' is a constant, radix sort takes linear time, O(n). Note however that if all of the numbers in the array are different then v is at least O(n), so O(log(n)) passes are needed, O(n.log(n))-time overall..
If a temporary array is used, the extra work-space used is O(n). It is possible do the sorting on each digit-position in-situ and then only O(log(n)) space is needed to keep track of the array sections yet to be processed, either recursively or on an explicit stack.
The radix sort is easily made stable if a temporary array is used. It is not stable if the sorting is in-situ.
[*]Even then there were other languages such as Algol-60, APL, Cobol, Lisp. Paper tape was an alternative to punched cards.
[+] L. Allison, one who was saved,
School of Computer Science & Software Engineering, Monash University, 1999.