import java.util.*;

public class RadixSortMain
{
	public static void main (String[ ] args)
	{
		int[ ] intArray = {59,  46,  32,  80,  46,  55,  50,  43,  44,  81,
				  12,  95,  17,  80,  75,  33,  40,  61,  16,  87};

		radixSort (intArray);
		for (int i : intArray)
			System.out.print (i + " ");
	} // method main


	/**
 	 *  Sorts a specified array into ascending order.
 	 *  The worstTime(n) is O(n log N), where n is the length of the array, and N is the largest
 	 *  number (in absolute value) of the numbers in the array.
 	 *
 	 *  @param a - the array to be sorted.
 	 *
 	 */
	public static void radixSort (int [ ] a) 
	{
	      	final int RADIX = 10;

      		int biggest = a [0],
           	    i;

      		for (i = 1; i < a.length; i++)
          		if (a [i] > biggest)
              			biggest = a [i];

      		int maxDigits = (int)Math.floor (Math.log (biggest) / Math.log (10)) + 1;

      		long quotient = 1;  // the type is long because the largest number may have
                                    // 10 digits; the successive quotients are 1, 10, 100, 1000,
				    // and so on.  10 to the 10th is too large for an int value.

      		LinkedList[ ] lists = new LinkedList [RADIX];

      		for (int m = 0; m < RADIX; m++)
          		lists [m] = new LinkedList<Integer>();

      		// Loop once for each digit in the largest number:
      		for (int k = 0; k < maxDigits; k++) 
     		{
          		// Store each int in a as an Integer in lists at 
			// the index of a [i]’s kth-smallest digit:
          		for (i = 0; i < a.length; i++)
              			((LinkedList<Integer>)lists [(int)(a [i] / quotient) % 
						RADIX]).add (a [i]);
          		i = 0;

			// Store each Integer in list [0], list [1], ...
 			// as an int in a:
			for (int j = 0; j < RADIX; j++) 
          		{
              			for (Integer anInt :  (LinkedList<Integer>)lists [j])
                     			a [i++] = anInt;   // unboxing
              			lists [j].clear();
          		} // for j
          		quotient *= RADIX;
      		} // for k
  	} // method radixSort

} // class RadixSortMain