/* Counting sort in C
  Source: http://en.wikipedia.org/wiki/Counting_sort
  This code is licensed under the Creative Commons Attribution-ShareAlike License.
  It is from the Wikipedia article "Counting sort" dated 2010-02-06. */

/* Counting sort (sometimes referred to as ultra sort or math sort)
is a sorting algorithm which (like bucket sort) takes advantage of
knowing the range of the numbers in the array to be sorted (array A). It
uses this range to create an array C of this length. Each index i in
array C is then used to count how many elements in A have the value i;
then counts stored in C can then be used to put the elements in A into
their right position in the resulting sorted array. The algorithm was
created by Harold H. Seward in 1954. */

void counting_sort(int *array, int size)
{
 int i, min, max;

 min = max = array[0];
 for(i = 1; i < size; i++)
 {
   if (array[i] < min)
    min = array[i];
   else if (array[i] > max)
    max = array[i];
 }

 int range = max - min + 1;
 int *count = (int *) malloc(range * sizeof(int));

 for(i = 0; i < range; i++)
   count[i] = 0;

 for(i = 0; i < size; i++)
   count[ array[i] - min ]++;
 int j, z = 0;
 for(i = min; i <= max; i++)
   for(j = 0; j < count[ i - min ]; j++)
    array[z++] = i;

 free(count);
}