Radix Sort

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!

function pass(a, N, dig)  // e.g. in JavaScript              //A C 1
// pre:  a[1..N] is sorted on digits [dig-1..0]                l o 9
// post: a[1..N] is sorted on digits [dig..0]                  g m 9
 { var counter = new Array(11); // for digit occurrences         p 9
   var temp = new Array();                                   //D .
   var i, d;                                                 //S S
                                                             //  c
   for( d = 0; d <= 9; d++ ) counter[d] = 0;                 //  i
   for( i = 1; i <= N; i++ ) counter[ digit(a[i], dig) ] ++;
   for( d = 1; d <= 9; d++ ) counter[d] += counter[d-1];

   for( i = N; i >= 1; i-- )
    { temp[ counter[ digit(a[i], dig) ] -- ] = a[i]; }

   for( i = 1; i <= N; i++ ) a[i] = temp[i];
 }//pass

function radixSort(a, N)
 { var p;
   for( p=0; p < NumDigits; p++ )
      pass(a, N, p);
 }//radixSort

// e.g. number = 1066
//        digit 3^  ^digit 0

--- Radix Sort for Ints in range [0..base^NumDigits-1]. ---

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. NB. Fortran is still popular for scientific and numerical computing.

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:

Complexity

Time

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(log_b(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..

Space

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.

Stability

The radix sort is easily made stable if a temporary array is used. It is not stable if the sorting is in-situ.

Notes

• See Sedgewick, Algorithms in C, edn 1, chapter 10, 1990.
• Radix sort in base ten was very natural for humans using the card sorting machine, but any base can be used and base two is natural for computers. A very large value for b, e.g. 1024 or more, can also be used, reducing the number of passes at the expense of increased space for more frequency counters.
• The algorithm can be adapted to mixed radix systems, e.g., £, shillings and (old) pence.
• There is a different radix sort algorithm which uses the same basic pass routine but sorts on the most significant digit first:
  1. Sort on digit position 'dig'.
  2. Sort (recursively) each of the regions of a[ ] associated with a particular digit value.
  This radix exchange sort can be thought of as a variation on quick sort.