Counting sort — O(n + k), integer keys only: Visual walkthrough

Step 1 — The problem, drawn as blocks

WHAT. We have a row of $n$ items. Each item carries a key — a small whole number. Our job: rearrange them so keys go from smallest to largest.

WHY start here. Before any algorithm, we need to see what we own. Every item is a block; the number written on it is its key. Sorting = sliding blocks along a shelf until the numbers rise left-to-right.

PICTURE. The top row is the input $A$ . Below it, the goal row — same blocks, reordered. Notice we haven't decided how to get there yet. We only know:

$n$ = how many blocks (here $n = 8$ ).
$k$ = the largest key that can appear (here $k = 5$ , so keys live in ${0, 1, 2, 3, 4, 5}$ ).

The whole trick that follows: we will never ask "is block A bigger than block B?" We only ask "how many blocks have value $v$ ?" — using $v$ itself as a shelf address.

Step 2 — Count how many of each value (the tally)

WHAT. Make a fresh array count with one cell per possible value, i.e. indices $0$ through $k$ . Set all to zero. Walk through $A$ once; for each block of value $v$ , add $1$ to count[v].

WHY. To place value $v$ later, we first need to know how many $v$ 's exist. You can't decide where the $3$ 's go until you know there are three of them. This scan costs $O (n)$ : one touch per block.

PICTURE. Watch the arrows: each block drops a tally mark into its own column. The block labelled $3$ always aims at column $3$ — the key is the address. That's the non-comparison heart of the method.

cell for value v count[v] + = 1 for each block with key v

count[v] — the counter belonging to value $v$ .
$+ = 1$ — bump it by one every time we meet that value.

After scanning all of $A$ :

count = [0 ’s 2, 1 ’s 0, 2 ’s 2, 3 ’s 3, 4 ’s 0, 5 ’s 1]

Step 3 — Turn counts into positions with a prefix sum

WHAT. Replace each count[v] by the running total of everything up to and including $v$ :

count [v] \leftarrow i = 0 \sum v count [i] .

WHY THIS TOOL — why a prefix sum and not something else? We want each value's final position on the shelf. A value $v$ 's block starts right after all smaller values have been laid down. "How many blocks are $\leq v$ ?" is precisely a cumulative sum of the tallies. No other operation converts "how many of each" into "where does each end" in one linear pass. This is the exact tool for the exact question.

PICTURE. Each bar grows by absorbing the bar to its left. The dotted stack on the right shows the shelf filling up: after the sweep, the height of column $v$ is the first free index past $v$ 's block.

new value count [v] = how many v ’s count [v] + everything below v count [v - 1]

Applied left to right, $[2, 0, 2, 3, 0, 1]$ becomes:

count = [2, 2, 4, 7, 7, 8]

Now read it as a promise: count[v] = number of keys $\leq v$ .

Step 4 — Read a value's home block off the array

WHAT. Fix a value $v$ . Define two boundaries:

L (v) = # {keys < v} = count [v - 1], R (v) = # {keys \leq v} = count [v] .

Then value $v$ 's blocks occupy exactly output indices $L (v)$ up to $R (v) - 1$ .

WHY. This is why the prefix sum was worth doing. Everything smaller than $v$ takes the first $L (v)$ slots. Everything equal to $v$ comes next, and there are $c_{v} = R (v) - L (v)$ of them, filling $[L (v), R (v) - 1]$ . Nothing overlaps, nothing is skipped — the blocks tile the shelf perfectly.

PICTURE. The shelf is coloured into contiguous blocks. For value $3$ : $L (3) = count [2] = 4$ and $R (3) = count [3] = 7$ , so the three $3$ 's own slots $4, 5, 6$ .

value v lives in [first slot L (v), last slot R (v) - 1], width = c_{v} = R (v) - L (v)

Recall Check the block widths against the tally

Value $0$ : $[0, 1]$ width 2. Value $2$ : $[2, 3]$ width 2. Value $3$ : $[4, 6]$ width 3. Value $5$ : $[7, 7]$ width 1. Total $2 + 2 + 3 + 1 = 8 = n$ . ✓

Step 5 — Place the blocks (scan input right-to-left)

WHAT. For each block in $A$ , taken from the last toward the first, with key $v$ :

count [v] - = 1; output [count [v]] = block .

Decrement first, then write.

WHY the direction matters. count[v] currently holds $R (v)$ — one past the block. Decrementing gives $R (v) - 1$ , the highest free slot for $v$ . We fill $v$ 's block from its back. Because we also read $A$ from its back, the last $v$ in the input claims the last slot — so equal keys keep their original order. That property is called stability.

PICTURE. Follow the trace: the rightmost input block is a $2$ ; it walks to the top of column $2$ 's block. The next-from-right is another value, and so on. Each write pulls the column's ceiling down by one.

claim highest free slot for v count [v] - = 1 ⟹ drop it there output [count [v]] = block

Full trace on $A = [2, 5, 3, 0, 2, 3, 0, 3]$ , reading right→left:

block read	$v$	`count[v]` before → after	write index
`3` (last)	3	7 → 6	out[6]=3
`0`	0	2 → 1	out[1]=0
`3`	3	6 → 5	out[5]=3
`2`	2	4 → 3	out[3]=2
`0`	0	1 → 0	out[0]=0
`3`	3	5 → 4	out[4]=3
`5`	5	8 → 7	out[7]=5
`2` (first)	2	3 → 2	out[2]=2

Result: $[0, 0, 2, 2, 3, 3, 3, 5]$ . Sorted — and not a single comparison was made.

Step 6 — Edge case: negative or shifted keys

WHAT. Array indices start at $0$ ; you cannot write count[-2]. If keys are $[- 2, 3, - 2, 0]$ , shift each key by $- min$ so the smallest maps to index $0$ :

index (v) = v - min, k = max - min .

Sort on shifted indices, then add $min$ back to recover the real values.

WHY. Counting sort's superpower is value = address. Addresses must be non-negative and start at $0$ . Subtracting the minimum slides any contiguous integer range down onto $[0, k]$ without changing the order.

PICTURE. The number line slides right by $2$ : $- 2 \to 0$ , $0 \to 2$ , $3 \to 5$ . Same gaps, same order, now index-friendly.

[- 2, 3, - 2, 0] - m i n = + 2 [0, 5, 0, 2] sort [0, 0, 2, 5] + m i n = - 2 [- 2, - 2, 0, 3]

The one-picture summary

Count → prefix-sum → place-from-the-back. Three linear sweeps, zero comparisons. The figure below stacks all three phases so you can see the tally become boundaries become homes.

Recall Feynman retelling — explain it to a friend

"Imagine sorting exam papers by a score from 0 to 5. First, I make six pigeonholes and just tally how many papers got each score — no reading, no comparing, one glance per paper. Second, I add the tallies up as I go, so each pigeonhole now tells me how many papers scored at most this much — which is the same as where this score's block ends on the final stack. Third, I deal the papers back onto the stack, but I go through my pile from the bottom up and drop each paper at the top of its score's block, then lower that ceiling by one. Going bottom-up means two papers with the same score never swap places — the sort stays honest (stable). That's it: count, add up, deal from the back. It's blazing fast because the score is the address, but it only works when the scores are small whole numbers I can use as pigeonhole labels."

Flashcards

Why does counting sort avoid the

Ω (n lo g n)

barrier?

It never compares two elements; it uses each key as an array index (

O (1)

random access), so the comparison-tree lower bound doesn't apply.

After the prefix sum, what does count[v] mean?

The number of keys

\leq v

— equivalently the index one past value

v

's block, i.e.

R (v)

What are

L (v)

and

R (v)

L (v) =

#keys

< v =

count[v-1];

R (v) =

#keys

\leq v =

count[v]. Value

v

occupies output indices

[L (v), R (v) - 1]

During placement, why decrement count[v] before writing?

count[v] holds

R (v)

, one past the block; decrementing gives the highest free slot

R (v) - 1

Why scan the input right-to-left when placing?

So the last equal key lands in the last slot, preserving original order → stability.

How do you counting-sort negative keys?

Shift by

- min

(index

= v - min

k = max - min

), sort, then add

min

back.

When must you NOT use counting sort?

When

k ≫ n

(e.g. 32-bit keys) — space/time blow up to

O (k)