Radix Sort
by Isai Damier, Android Engineer @ Google

/****************************************************************************
 * Author: Isai Damier
 * Title: Radix Sort
 * Project: geekviewpoint
 * Package: algorithms
 *
 * Statement:
 *   Given a disordered list of integers, rearrange them in natural order.
 *
 * Sample Input: {18,5,100,3,1,19,6,0,7,4,2}
 *
 * Sample Output: {0,1,2,3,4,5,6,7,18,19,100}
 *
 * Time Complexity of Solution:
 *   Best Case O(k*n); Average Case O(k*n); Worst Case O(k*n),
 *   where k is the length of the longest number and n is the
 *   size of the input array.
 *
 *   Note: if k is greater than log(n) then an n*log(n) algorithm would be a
 *         better fit. In reality we can always change the radix to make k
 *         less than log(n).
 *
 * Approach:
 *   radix sort, like counting sort and bucket sort, is an integer based
 *   algorithm (i.e. the values of the input array are assumed to be
 *   integers). Hence radix sort is among the fastest sorting algorithms
 *   around, in theory. The particular distinction for radix sort is that it
 *   creates a bucket for each cipher (i.e. digit); as such, similar to
 *   bucket sort, each bucket in radix sort must be a growable list that may
 *   admit different keys.
 *
 *   For decimal values, the number of buckets is 10, as the decimal system
 *   has 10 numerals/cyphers (i.e. 0,1,2,3,4,5,6,7,8,9). Then the keys are
 *   continuously sorted by significant digits.
 ***************************************************************************/ 
 public void radixsort(int[] input) {
  final int RADIX = 10;
  // declare and initialize bucket[]
  List<Integer>[] bucket = new ArrayList[RADIX];
  for (int i = 0; i < bucket.length; i++) {
    bucket[i] = new ArrayList<Integer>();
  }

  // sort
  boolean maxLength = false;
  int tmp = -1, placement = 1;
  while (!maxLength) {
    maxLength = true;
    // split input between lists
    for (Integer i : input) {
      tmp = i / placement;
      bucket[tmp % RADIX].add(i);
      if (maxLength && tmp > 0) {
        maxLength = false;
      }
    }
    // empty lists into input array
    int a = 0;
    for (int b = 0; b < RADIX; b++) {
      for (Integer i : bucket[b]) {
        input[a++] = i;
      }
      bucket[b].clear();
    }
    // move to next digit
    placement *= RADIX;
  }
}
import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

  @Test
  public void testRadixsort() {
    System.out.println(""radixsort"");
    int[] input = {18, 5, 100, 3, 1, 19, 6, 0, 7, 4, 2};
    Sorting instance = new Sorting();
    instance.radixsort(input);
    for (int i = 1; i < input.length; i++) {
      if (input[i - 1] > input[i]) {
        fail(""radixsort method fails."");
      }
    }
  }
}