Why does counting sort copy the input elements?

Question

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.

Answer 1

They do not need to do it this way, but they might have found it more elegant.

Their idea is not:

Put every element j in 0..k-1 into b exactly c[j] times.

But rather:

Use the counts to compute the position of every a[i] in b.

That is what the second loop is for: it subsequently computs the offsets for the block of elements i in b.
(The should use j here to avoid confusing, but well.)

As KWillets notes, the latter idea lends itself¹ better to sorting more complex data, say objects, by an integer key; then you would need to copy the references in proper order. Note how it is even stable!

On the other hand, if you do not need resp. make use of this, I expect the first idea to be much more efficient in practice: observe how the second implementation makes non-sequential accesses to arrays b and c which may cause a lot more cache misses than the alternative.

---

1. The given implementation can only sort integer arrays, of course.