Counting Sort

Counting sort is a non-comparison sorting algorithm for integer keys in a known range 0..k. It tallies how many times each key occurs, converts the tallies into positions with a prefix sum, then writes every element directly into its final slot — O(n + k) time, O(n + k) extra space, and stable.

Here is the trick in one sentence: if you know how many keys are smaller than or equal to yours, you know exactly where you belong — no need to compare yourself with anyone. It works like a seating chart for a wedding. You don't seat guests by asking each pair who outranks whom; you count the RSVPs per family, run a quick running total to find where each family's block of seats starts, and then walk guests straight to their chairs. Counting sort never compares two elements. Not once.

Counting Sort Turns Counts into Addresses

The algorithm is three loops, and each one is doing something different with the same little array.

First, the tally. Walk the input once and increment count[v] for every element v. When this loop ends, count is a histogram: count[3] = 3 means the key 3 appears three times. The element itself is only ever used as an index into the count array — that is the whole non-comparison move.

Second, the prefix sum. Sweep the count array left to right, adding each cell into the next: count[i] += count[i - 1]. This is the beat where the array changes meaning under your feet. Before the sweep, count[3] said "there are three 3s." After it, count[3] says "seven keys are ≤ 3" — which is the seating-chart fact: the block of 3s ends at position 6, because seven guests sit at or before it. Same cells, new units: counts became addresses.

The Backward Walk Keeps Counting Sort Stable

The third loop is the placement. Allocate the output array, then walk the input backward. For each element v, decrement count[v] and write v at out[count[v]]. One subtraction, one write, straight to the final position. No probing, no shifting, no second look.

Why backward? Stability. After the prefix pass, count[v] points one past the last slot reserved for v. The backward walk meets the last v in the input first and gives it that last slot; the next-to-last v gets the slot to its left, and so on. Equal keys land right to left exactly as the input listed them right to left — original order preserved. Run the same loop forward and every value still lands in the correct block, but equal keys come out reversed. The array looks sorted; the stability is quietly gone. This matters beyond aesthetics: radix sort runs a counting sort per digit and is only correct because each pass is stable.

Counting Sort Step by Step

The visualization runs [2, 5, 3, 0, 2, 3, 0, 3] — eight keys, k = 5, with enough duplicates that stability is visible. Equal keys wear small badges (3ᵃ, 3ᵇ, 3ᶜ in input order) so you can watch order survive.

1. Tally. The scan visits each element left to right and bumps its cell: the two 0s make count[0] = 2, the two 2s make count[2] = 2, the three 3s make count[3] = 3, the lone 5 makes count[5] = 1. Result: count = [2, 0, 2, 3, 0, 1].
2. Prefix sum. Left to right, each cell absorbs its neighbor: [2, 2, 4, 7, 7, 8]. Read count[3] = 7 as "seven keys ≤ 3."
3. Place 3ᶜ. The backward walk starts at arr[7] = 3. Decrement count[3] from 7 to 6, write out[6] = 3. The last 3 takes the last slot of the 3-block.
4. Place 0ᵇ. arr[6] = 0: count[0] drops 2 → 1, so out[1] = 0.
5. Place 3ᵇ. arr[5] = 3: count[3] drops 6 → 5, so out[5] = 3 — one slot left of 3ᶜ. That is stability happening in real time.
6. The remaining five placements repeat the pattern: 2ᵇ → out[3], 0ᵃ → out[0], 3ᵃ → out[4], 5 → out[7], 2ᵃ → out[2]. Output: [0, 0, 2, 2, 3, 3, 3, 5], badges reading a-b-c inside every block.

On the canvas, the count row sits between input and output because it is literally the middleman: watch a +1 pulse drop into a cell during the tally, the row's label flip from count to addresses after the prefix sweep, and each card fly through its address cell to the output slot it computed. When a duplicate lands, the status line names the moment and a green bracket gathers the equal-key block below the output — badges reading in input order, the proof that stability held.

Time and Space Complexity

Space is O(n + k): the output array plus one count cell per possible key. Counting sort is stable and not in-place, and its time complexity does not depend on the input's initial order at all — a sorted input costs exactly the same as a shuffled one.

The fine print is the k. Those bounds are a bargain while k stays near n, and a disaster when it doesn't: sorting four values spread across keys 0..29 allocates 30 cells and drags the prefix sweep through 29 of them — the Scenarios panel ships exactly that input so you can feel O(k) in the scrubber. Push k to a billion and the count array is a billion cells for the same four elements. That, in one array, is why comparison sorts still exist. (The visualization caps keys at 30 — a canvas budget, not a property of the algorithm.)

Edge Cases

• Empty array. max(arr) has nothing to take a max of and throws; real implementations guard for it first. The visualization requires at least one element.
• Single element. One tally, one placement. The prefix sweep still runs over the key range below it.
• All keys equal. One hot cell holds the whole count; the output fills from a single address counting down, badges in input order.
• All zeros. k = 0, so the prefix loop runs zero times — the tally is already the address book.
• k much larger than n. Correct but wasteful; see the fine print above.

Common Mistakes

• Walking the final loop forward. The output is still sorted, so tests that only check order will pass — while equal keys silently reverse. Sort records by key instead of bare integers and the bug surfaces immediately.
• Writing before decrementing. After the prefix pass, count[v] is one past the last slot for v. Write first and you overflow the block by one; the decrement-then-write order is load-bearing.
• Sizing the count array by n. It needs k + 1 cells, one per possible key — max(arr) + 1, not len(arr). The two agree just often enough in toy tests to hide the bug.
• Feeding it the wrong keys. Negative integers need an offset shift first, and floats or strings have no count cell at all. Counting sort is an integer-keys specialist, not a general-purpose sort.