Counting sort

Counting Sort - a sorting algorithm which takes advantage of knowing the maximum value within the array to be sorted and uses this to create an array (referenced by the values within the array to be sorted) that will serve to count the number of values of a certain number and, after this, the future positions of the values on a third array, which is the sorted permutation of the second array (i.e., A[i] <= A[j], i < j). This algorithm is stable. C code snippet follows:

void counting_sort (int *A, int k) {

 int *B = malloc (length(A)*sizeof(int));
 int *C = malloc (k+1*sizeof(int));
 for (i = 0; i <= k; ++i)
   C[i] = 0;
 for (i = 0; i < length(A); ++C[A[i]], ++i);
 /* C[i] now contains the number of elements equal to i */
 for (i = 1; i < k; C[i] += C[i - 1], ++i);
 /* C[i] now contains the number of elements less than or equal to i */
 for (i = length(A); i > 0; --C[A[i]], --i)
   B[C[A[i]]] = A[i];
 /* we use C to allocate the element that is required onto the new array B */
 free (C);
 for (i = 0; i < length(B); ++i)
   A[i] = B[i];
 free (B);

}