When I was reading about counting sort in Introduction to Algorithms for the first time, I stopped reading after the step where they calculate the number of each element in the input array. It's the first thing we do after allocating an auxiliary array.
I was sure the algorithm would look like this:
public static int[] countingSort2(int[] input, int k) {
// 0 <= input[i] < k
int[] result = new int[input.length];
int[] auxiliary = new int[k];
for (int j = 0; j < input.length; j++) {
auxiliary[input[j]] = auxiliary[input[j]] + 1;
}
int resultIndex = 0;
for (int i = 0; i < auxiliary.length; i++) {
if (auxiliary[i] != 0) {
for (int m = 0; m < auxiliary[i]; m++) {
result[resultIndex++] = i;
}
}
}
return result;
}
But of course, the canonical implementation is different:
public static int[] countingSort(int[] a, int k) {
int c[] = new int[k];
for (int i = 0; i < a.length; i++)
c[a[i]]++;
for (int i = 1; i < k; i++)
c[i] += c[i - 1];
int b[] = new int[a.length];
for (int i = a.length - 1; i >= 0; i--)
b[--c[a[i]]] = a[i];
return b;
}
I wonder why they needed to fill the auxiliary array again and then put elements of the input array to the output array.