Counting sort

If every score is a whole number from 0 to 9, count how many marks got each score, and every mark knows where it goes. Watch: no two marks are ever compared.

⋯6struct mark {7    int score;8    char id;9};10 11void counting_sort(const struct mark *in, struct mark *out, int n)12{13    int count[K] = { 0 };14    for (int i = 0; i < n; i++)15        count[in[i].score]++;16    for (int m = 1; m < K; m++)17        count[m] += count[m - 1];18    for (int i = n - 1; i >= 0; i--) {19        count[in[i].score]--;20        out[count[in[i].score]] = in[i];21    }22}

Count, total, place

Suppose every key is a whole number from 0 to k − 1, here a score from 0 to 9. Then sorting needs no comparisons. Three passes do it:

1. Count. For each item, add 1 to the counter of its key.
2. Total. Turn the counts into running totals: count[m] becomes the number of items with key m or less.
3. Place. The items with key m or less fill out[0] to out[count[m] − 1]. So the last item with key m goes in out[count[m] − 1]. Take the items from the right, and for each, subtract 1 from its counter and write it at that cell.

The keys are used as indices, into count, never compared with each other.

The code and its cost

struct mark {
    int score;
    char id;
};

void counting_sort(const struct mark *in, struct mark *out, int n)
{
    int count[K] = { 0 };
    for (int i = 0; i < n; i++)
        count[in[i].score]++;
    for (int m = 1; m < K; m++)
        count[m] += count[m - 1];
    for (int i = n - 1; i >= 0; i--) {
        count[in[i].score]--;
        out[count[in[i].score]] = in[i];
    }
}

With K = 10 and the twelve marks above:

Placing from the right: 7L goes to cell 9 − 1 = 8, 9K to 12 − 1 = 11, 5J to 6 − 1 = 5, and so on. marks.c prints 0F 3B 3D 3I 5E 5J 7A 7G 7L 8H 9C 9K.

The passes take n, k and n steps: O(n + k) time. Besides the input, it needs the k counters and an output array of n items: O(n + k) memory.

Stable

The three marks with score 3 were B, D, I in the input, and they come out as 3B 3D 3I. Placing from the right is what keeps them so: the rightmost 3, I, is placed first, into the last of the three cells for score 3; then D before it, then B. A sort that keeps equal keys in their input order is stable. That matters when the items carry more than the key, and it is what radix sort relies on (Radix sort).

Faster than any comparison sort

A sort that only compares items must, in effect, find out which of the n! possible orders the input is in (Counting). Each comparison has two outcomes, so at best it halves the orders still possible. Telling n! orders apart therefore takes at least log₂ n! comparisons in the worst case, which is about n log₂ n − 1.44n. No comparison sort beats O(n log n).

Counting sort escapes that bound because it never compares. It reads each key and uses it as an address, which only works because the keys are small integers.

Worked example

The bound for ten items. log₂ 10! = log₂ 3,628,800 ≈ 21.8. So no comparison sort can always sort ten items in fewer than 22 comparisons.

When the keys are too big. 1,000 items with keys up to 10⁹ would need k = 10⁹ counters, a million times more counters than items. Counting sort is the wrong tool here. Radix sort splits each key into small digits and counting-sorts one digit at a time.

Placing from the left. Run the last loop from i = 0 upwards instead, and the first 3 placed, B, takes the last cell for score 3. marks-left.c makes only that change and prints 0F 3I 3D 3B 5J 5E 7L 7G 7A 8H 9K 9C: every group of equal scores comes out reversed. The order of the scores is still right, but the sort is no longer stable.

Two checks. Where does the first 7, A, go? (Cell 6: when A is placed, count[7] has already gone from 9 to 7 for L and G, and goes down once more.) How much memory for k = 256 and n = 10⁶? (256 counters and an output of 10⁶ items.)

Where it’s used

Small keys, such as marks, ages and bytes. Sorting the bytes of a file takes 256 counters.

Inside radix sort, which counting-sorts one digit of the key per pass and needs every pass to be stable.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.