Lesson · Sorting and Selection · Not comparing at all

Counting Sort

If the keys are integers in 0 … k−1, they can be used as indices instead of being compared: tally them, turn the tally into a prefix sum, and place each record into the slot its prefix sum names. The cost is Θ(n + k), which is not a contradiction of the comparison lower bound because no two keys are ever compared. The placement pass runs from the back, and that direction is the whole of the algorithm's stability.

Open the interactive lesson Practice

tally[key] += 1 one pass over the n keys prefix[i] = prefix[i−1] + tally[i] one pass over the k counters for each record from the BACK: out[--prefix[key]] = record work = n + k 12 keys with k = 5: 17 12 keys with a 32-bit key: 4 294 967 308

Three passes, and the second term of the cost

Core ideas

What this lesson establishes

The hard idea is what the comparison lower bound is a bound on, which is a question about a model rather than about an algorithm.

Nothing is compared, so the bound does not apply

⌈log₂ n!⌉ is a lower bound for algorithms whose only access to the keys is a comparison, and it is proved by counting the leaves a decision tree needs. Counting sort never asks whether one key is at most another: it uses a key as an array index. So it is outside the theorem's hypothesis, not a counterexample to its conclusion. On 12 keys the bound is 29 comparisons and counting sort makes none, which settles nothing about the bound and everything about the model.

The prefix sum says where each run of equal keys ends

After tallying, prefix[i] is the number of keys at most i, so it is exactly the last output slot that key i may occupy, counting from one. On the lab's keys the tally is 1 2 2 3 4 and the prefix sums are 1 3 5 8 12: the four records with key 4 own slots nine to twelve, and prefix[4] = 12 names the last of them. That is why the placement pass counts down.

The placement direction is the stability

Walk the input from the back and write each record into prefix[key], decrementing as you go. The last record with a given key takes the last slot, the one before it takes the one before, and input order survives. Walk forward with the same bookkeeping and every run comes out reversed: the lab measures 11 reordered pairs on the same 12 keys. The algorithm is otherwise identical, which is what makes the direction worth a sentence in every description of it.

The material

A tally, a prefix sum, and a placement pass with a direction

The three passes, where the stability lives, and the term that decides whether this algorithm is worth using.

Definition · Counting sort

Counting sort sorts n records whose keys are integers in 0 … k−1. Tally the keys into an array of k counters. Replace the tally with its running totals, so that counter i holds the number of keys at most i. Then pass over the input from back to front, writing each record into the output slot its counter names and decrementing that counter.

Tally: k counters zeroed, then one increment per record. Cost Θ(n + k).
Prefix: one pass over the counters, replacing each with the running total. Cost Θ(k).
Place: one pass over the records, back to front, one write each. Cost Θ(n).

Example · Twelve keys in the range zero to four

The keys are 4 1 3 4 3 0 2 4 1 3 4 2. The tally is 1 2 2 3 4 — one zero, two ones, two twos, three threes, four fours — and the prefix sums are 1 3 5 8 12. Placing from the back gives 0 1 1 2 2 3 3 3 4 4 4 4 with the tags inside each run still ascending. The work is n + k = 17.

No branch in that procedure looked at two keys together. The comparison bound is silent, and the cost is the sum of two terms that have nothing to do with each other: n, the number of records, and k, the width of the declared key range.

The second term is the whole question

Θ(n + k) is called linear and is linear in n + k, which is not the same thing as linear in n. At 12 keys over a range of five, the work is 17 against n log₂ n ≈ 43, and counting sort wins comfortably. Declare a 16-bit key and the work is 12 + 65 536. Declare a 32-bit key and it is 4 294 967 308, and the counter array alone is four billion slots of memory for twelve records.

So the algorithm is chosen by a comparison of terms, not by a class. It is the right sort when k is O(n) or thereabouts: ages, bytes, digits, bucket indices, grades. It is the wrong sort when k is n², or a machine word, or unknown. The lab's range control only changes the second term, which is the term that decides.

Theorem · Backward placement is stable

If the placement pass visits the records from last to first, writing each into slot prefix[key] and then decrementing that counter, then records with equal keys appear in the output in the same relative order as in the input.

Fix a key value v, and let the records with that key be, in input order, r₁, r₂, …, r_t. Before any of them is placed, prefix[v] is the number of keys at most v, which is the last slot the run owns.

The pass visits them in the order r_t, r_{t−1}, …, r₁, and each visit takes the current value of prefix[v] and then decreases it by one. So r_t gets the last slot of the run, r_{t−1} the one before, and r₁ the first. The output order is r₁, …, r_t, which is the input order.

The same argument with the pass running forwards hands r₁ the last slot and r_t the first, reversing the run — which is not a bug in the bookkeeping but the same bookkeeping read the other way.

□

The lab runs both directions on the same keys and flags the reordered pairs: zero from the back, eleven from the front. The output is sorted either way. Only the order inside each run of equal keys differs, and that is precisely what radix sort needs, since it is d of these passes stacked and its correctness argument is nothing but their stability.

One more property is worth naming: counting sort is not in place. It needs n output slots and k counters, so it trades memory for the comparison it does not make. Heapsort was the other trade in the same two dimensions, and neither trade is implied by anything about Θ.

Interactive

Linear in n plus k, and k is not always small

A tally, a prefix sum and a placement direction that is the whole stability argument

Choose the keys, the declared range and the pass

The tally and the prefix sums are computed from the keys you type. The declared range only changes the second term of n + k, which is the term that decides whether this algorithm is worth using.

Keys

Declared key range k

Placement pass

Work n + k—

Any comparison sort needs at least—

Writes into the output—

Equal keys reordered—

Nothing here is compared, so the comparison lower bound does not apply and there is no contradiction to explain. What does apply is n + k: the second term is the declared range, and a range wide enough to be interesting is wider than n log n.

Method

Running counting sort, and sizing it first

The sizing question comes first, because it is the one that can rule the algorithm out.

Write down k before anything else

Not the largest key present: the width of the range the keys are drawn from, which is what the counter array has to cover. If k is much larger than n log n, stop here and use a comparison sort. This is the step the misconception skips.

Tally, and check the total

One counter per value in the range, one increment per record. The counters must sum to n; if they do not, a key was outside the range you declared and the algorithm has no defined behaviour for it.

Turn the tally into a prefix sum, and read it as slots

After the running totals, counter i is the number of keys at most i, which is the last output slot key i may occupy. Say that sentence out loud before placing anything; it is what makes the next step obvious rather than magic.

Place from the back, decrementing

Visit the input from last record to first. Write each into slot prefix[key], then decrement that counter. Going forwards with the same counters also sorts, and reverses every run of equal keys, so the direction is not a matter of taste.

State the cost as two terms and compare them

n + k, with both terms named. Put it beside n log₂ n at your n, and beside the ⌈log₂ n!⌉ the panel prints — remembering that the last of those is a number of comparisons and counting sort makes none, so it is a bound this algorithm is outside rather than one it beats.

Linear in what

Score 0 / 0

Choose the answer you can justify.

Twelve keys placed from the back, one record at a time

The keys are the lab's, tagged by input position so that stability is visible: 4#1 1#2 3#3 4#4 3#5 0#6 2#7 4#8 1#9 3#10 4#11 2#12. The range is just wide enough for the keys, so k = 5 and the counters cover 0 … 4.

keys 4 1 3 4 3 0 2 4 1 3 4 2 tags #1 #2 #3 #4 #5 #6 #7 #8 #9 #10 #11 #12 tally key 0 1 2 3 4 cnt 1 2 2 3 4 sums to 12 = n prefix key 0 1 2 3 4 cum 1 3 5 8 12 prefix[i] = how many keys are ≤ i placement, from the LAST record to the first #12 key 2 → slot 5 prefix[2] 5 → 4 #11 key 4 → slot 12 prefix[4] 12 → 11 #10 key 3 → slot 8 prefix[3] 8 → 7 #9 key 1 → slot 3 prefix[1] 3 → 2 #8 key 4 → slot 11 prefix[4] 11 → 10 #7 key 2 → slot 4 prefix[2] 4 → 3 #6 key 0 → slot 1 prefix[0] 1 → 0 #5 key 3 → slot 7 prefix[3] 7 → 6 #4 key 4 → slot 10 prefix[4] 10 → 9 #3 key 3 → slot 6 prefix[3] 6 → 5 #2 key 1 → slot 2 prefix[1] 2 → 1 #1 key 4 → slot 9 prefix[4] 9 → 8 output 0#6 1#2 1#9 2#7 2#12 3#3 3#5 3#10 4#1 4#4 4#8 4#11 work n + k = 12 + 5 = 17, and not one comparison between two keys

Follow the four records with key 4. They were placed in the order #11, #8, #4, #1 into slots 12, 11, 10, 9, and they come out reading #1, #4, #8, #11. The pass ran backwards and the run came out forwards, which is the whole of the stability argument written in one line of bookkeeping.

Now switch the placement control to run from the front and watch the same twelve records come out 0#6 1#9 1#2 2#12 2#7 3#10 3#5 3#3 4#11 4#8 4#4 4#1: still sorted by key, with every run reversed and eleven pairs flagged. The lab counts those pairs rather than asserting the property.

For a faded rehearsal, change the declared range to a byte, k = 256, without changing the keys. The supplied first move is the arithmetic: the work becomes 12 + 256 = 268, against n log₂ n ≈ 43. Say which algorithm you would now choose for twelve records, and then find the smallest n at which counting sort over a byte range wins again.

Common mistakes

Calling counting sort linear without naming k“Linear” on its own hides the term that decides. Write the cost as n + k with both numbers filled in, and the algorithm selects itself: 17 for twelve keys over a range of five, 4 294 967 308 for the same twelve keys over a 32-bit range. The second is not a slow sort; it is not a sort you can run.

Taking the largest key present as kThe counter array has to cover the range the keys are drawn from, because a key outside it has nowhere to be tallied. If the keys are 32-bit integers that happen to be small today, k is still 2³² unless something guarantees otherwise. The lab separates the two ideas by letting you declare a range wider than the keys you typed.

Expecting stability to come for freeNothing about tallying and prefix summing is stable or unstable; the placement direction decides, and the forward direction is exactly as short to write. Any description of counting sort that does not say which way the placement pass runs has left out the only line where stability lives — and radix sort is built entirely on that line.

Check your understanding

✓

Finish when you can size counting sort before running it, and say where its stability lives.

You should be able to tally and prefix-sum twelve keys by hand, place them from the back with the counters decrementing, state the cost as two named terms, and explain why making no comparisons puts this algorithm outside the comparison bound rather than above it.

Note: Counting sort needs k counters, which rules it out for wide keys. Split a wide key into digits and the range per pass becomes the base rather than the key's whole domain — and then the passes have to be composed, which is a question about stability. That is “Radix Sort”, and the stability proved above is the only thing its correctness rests on.