1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ That's mainly to allow sorting of things with more attributes than just the key. The original elements have to be moved instead of duplicating the key. $\endgroup$ – KWillets Oct 16 '16 at 20:42
  • $\begingroup$ @KWillets No, the algorithm won't work at all with anything but an integer array. $\endgroup$ – Raphael Oct 17 '16 at 8:29
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.