Radix Sort

Radix sort is a non-comparison sort that runs in linear time under certain space assumptions (see analysis below).

Algorithm

To sort n k-digit (in radix r) items in array a:

// r is the radix
// k is the number of digits in each item in radix r
// i is the pass (which digit we're sorting on)
// place is the place value of this digit in radix r
// count[i] holds the # of elements whose ith digit is <= i
// b is an auxiliary n-element array 

// Note that (a[j]/place)%r is the "place" digit; e.g., if place=10, it's
// the 10s digit.

// Numbers (1), (2), etc are used in analysis below

for (int i=0, place = 1; i < k; i++, place*=r)
   {
	// initialize count (1)
	for (int j=0; j<r; j++)
	    count[j]=0;  

	// count # elements with each digit in this place (2)
	for (int j=0; j<N; j++)
	    count[(a[j]/place)%r]++;

	// accumulate array count (3)
	for (int j=1; j<r; j++)
	    count[j] += count[j-1];

	// sort by ith digit into array b, working backwords from
	// a to keep each pass stable (4)
	for (int j=N-1; j>=0; j--)
	    b[--count[(a[j]/place)%r]] = a[j];
 
	// copy back to a in preparation for next pass (5)
	for (int j=0; j<N; j++)
	    a[j] = b[j];
    }

Analysis

The out loop executes k times. Inside this loop, the complexity of each loop is as follows:

  (1) r
  (2) N
  (3) r
  (4) N
  (5) N

So the overall complexity is O(k(N+r)). Radix r is typically small, so we treat it as a constant. Then if k (the number of digits) is constant, radix sort is O(N). But if the N values are distinct, k must be at least log_rN, giving a time of O(NlogN). Alternatively, the value of k can be decreased by increasing r. In particular, we can fix k by letting r vary; e.g., r=2^((log₂N)/k) processes log₂N/k bits at a time. process Since 2^((log₂N)/k) < N, this gives a linear sort.

Example: Let k=4. Then for a 32-bit word -- representing 2^32 different integers -- r=2^(32/4) = 2^8 = 256. This sounds big until you think that this supports up to 2^32 distinct values -- very large N.