/**
* Sorts an array of N int's assuming the int's are in the range [0:M].
* Implements counting sort algorithm.
* @author Dung X. Nguyen - Copyright (c0 1999 - All rights reserved.
* @since 11/30/99
*/
public class CountSorter
{
   private int[] _sortedElts;
   private int[] _cntrs; // _cntrs[k] == how many k's there are.

   public static void main(String[] args)
   {
      int[] A = {99, 34, 0, 5, 7, 0};
      System.out.println ("A =");
      for (int i = 0; i < A.length; i++)
      {
         System.out.print (A[i] + "  ");
      }
      System.out.println ();
      System.out.println ("Sorting A...");
      new CountSorter (A.length, 99).sort (A);
      System.out.println ("Sorted A =");
      for (int i = 0; i < A.length; i++)
      {
         System.out.print (A[i] + "  ");
      }
      System.out.println ("\nDone");
	}
 
   public CountSorter(int numElts, int maxElt)
   {
      _sortedElts = new int[numElts];
      _cntrs = new int[maxElt + 1];
   }

   public final void sort (int[] elts)
   {
      _zeroCounters ();       // cntrs[k] == 0.
      _countElements (elts);  // _cntrs[k] == how many k's there are in elts.
      _computeIndices ();     // _cntrs[k] == number of elements <= k in elts.
      _fillSortedElts (elts); // _sortedElts[] is filled with elements of elts in sorted order.
      _copySortedElts2Elts (elts); // elts[] is sorted.
   }

   private final void _zeroCounters ()
   {
      for (int k = 0; k < _cntrs.length; _cntrs[k++] = 0);
   }

   private final void _countElements (int[] elts)
   {
      for (int ix = 0; ix < elts.length; ix++)
      {
         _cntrs[elts[ix]]++;
      }
   }

   private final void _computeIndices ()
   {
      int k = 1;
      // Invariant: _cntrs[k-1] is the number of elements <= k- 1 in elts[]. 
      for (k = 1; k < _cntrs.length; k++)
      {
         _cntrs[k] += _cntrs[k-1];
      }
   }

   private final void _fillSortedElts (int[] elts)
   {
      for (int ix = elts.length - 1; ix >= 0; ix--)
      {
         _sortedElts[_cntrs[elts[ix]]- 1] = elts[ix];
         _cntrs[elts[ix]]--;
      }
   }

   private final void _copySortedElts2Elts (int[] elts)
   {
      for (int ix = 0; ix < elts.length; elts[ix] = _sortedElts[ix], ix++);
      // for (int ix = 0; ix < elts.length; elts[ix] = _sortedElts[ix++]); // OK!
      // for (int ix = 0; ix < elts.length; elts[ix++] = _sortedElts[ix]); // ?!?! DIE !! WHY?
   }
}