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++)

    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.

  • 2
    $\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, 2016 at 20:42
  • $\begingroup$ @KWillets No, the algorithm won't work at all with anything but an integer array. $\endgroup$
    – Raphael
    Oct 17, 2016 at 8:29
  • $\begingroup$ @Raphael I don't think that's true. Imagine an array of Car objects. You could sort them using this algorithm by mileage or color or any other attribute that is reducible to an integer value. $\endgroup$ Oct 21, 2022 at 16:02

1 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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