Counting sort — O(n + k), integer keys only: Worked examples

This page is a case gauntlet. The parent Counting Sort note taught you the three steps (Tally → Prefix sum → Place right-to-left). Here we make sure that no input can surprise you. We enumerate every kind of input counting sort can face, then work one full example per kind.

The scenario matrix

Every counting-sort input falls into one of these case classes (recall $n$ = item count, $k$ = max key). The examples below are labelled with the cell they cover.

#	Case class	What's special	Example
C1	Plain non-negative ints	the textbook happy path	Ex 1
C2	All keys equal (degenerate)	one bucket holds everything	Ex 2
C3	Empty / single element	$n = 0$ and $n = 1$ boundaries	Ex 3
C4	Negative keys	need a min-offset shift	Ex 4
C5	Sparse range, $k ≫ n$	many empty buckets — waste warning	Ex 5
C6	Records + stability	equal keys must keep order	Ex 6
C7	Word problem (real world)	modelling a real count	Ex 7
C8	Exam twist — sort descending	reverse without breaking stability	Ex 8

Together C1–C8 touch every sign (positive, zero, negative), every degenerate shape (empty, singleton, all-equal), the limiting behaviour ( $k ≫ n$ ), a real application, and a twist.

Before we start, picture the three arrays we keep manipulating. The figure below shows them for the very first example ( $A = [4, 1, 3, 1, 4, 0]$ ): the lavender input keys, the mint count array (one cell per possible value $0.. k$ ), and the butter output slots that get filled last.

Figure — Counting sort — O(n + k), integer keys only

Notice three separate arrays, three different lengths: input and output both have length $n = 6$ , while count has length $k + 1 = 5$ . The coral arrows show the two data flows we trace in every example — count (input → count) and place (count → output).

Worked examples

Ex 1 — C1: plain non-negative integers

Worked example Sort

$A = [4, 1, 3, 1, 4, 0]$ , keys in $[0, 4]$ so $k = 4$ . Forecast: guess the final array before reading on. (Sorted it is obviously $[0, 1, 1, 3, 4, 4]$ — but trace the machinery that produces it. This is the array drawn in the figure above.)

Step 1 — Tally. count = [0]*(k+1) = [0,0,0,0,0]. Scan $A$ and bump: value 0→1, 1→2, 3→1, 4→2. $count = [1, 2, 0, 1, 2]$ Why this step? We must know how many copies of each value exist before we can reserve slots.

Step 2 — Prefix sum. Replace each cell with the running total left-to-right: $count = [1, 1 + 2, 3 + 0, 3 + 1, 4 + 2] = [1, 3, 3, 4, 6]$ Why this step? Now count[v] = number of keys $\leq v$ . That number is the index just past $v$ 's block, so count[v]-1 is the last slot value $v$ may occupy.

Step 3 — Place (scan $A$ right→left). out = [None]*6.

0: count[0]:1→0, out[0]=0
4: count[4]:6→5, out[5]=4
1: count[1]:3→2, out[2]=1
3: count[3]:4→3, out[3]=3
1: count[1]:2→1, out[1]=1
4: count[4]:5→4, out[4]=4

Why right→left? So equal keys stay in original order (stability). Here it also just works.

Result: $[0, 1, 1, 3, 4, 4]$ .

Verify: matches Python's sorted(A). Multiset unchanged: two 4's, two 1's, one 0, one 3. ✓

Ex 2 — C2: all keys identical (degenerate)

Worked example Sort

$A = [7, 7, 7, 7]$ , $k = 7$ . Forecast: nothing to reorder — but does the machinery survive a single crowded bucket?

Step 1 — Tally. count has size 8 (indices 0..7). Only bucket 7 fills: $count = [0, 0, 0, 0, 0, 0, 0, 4]$ Why this step? Even when everything lands in one bucket, we still count it — the algorithm makes no special case.

Step 2 — Prefix sum. Running totals: all zeros until index 7, which becomes 4: $count = [0, 0, 0, 0, 0, 0, 0, 4]$ Why this step? count[7]=4 says "4 keys are $\leq 7$ ", so value 7 owns slots $0..3$ .

Step 3 — Place (right→left).

7: count[7]:4→3, out[3]=7
7: count[7]:3→2, out[2]=7
7: count[7]:2→1, out[1]=7
7: count[7]:1→0, out[0]=7

Result: $[7, 7, 7, 7]$ .

Verify: length preserved, all values 7, no index went negative or out of range. ✓ Degenerate input handled with zero special-casing.

Ex 3 — C3: empty and singleton (boundary $n = 0$ , $n = 1$ )

Worked example Sort

$A = []$ (empty) and separately $A = [5]$ with $k = 5$ . Forecast: these should be no-ops. The danger is an off-by-one crash on a zero-length loop.

Empty case, $n = 0$ :

Tally loop runs zero times — count = [0]*(k+1) stays all zeros. Why fine? Looping over an empty list does nothing.
Prefix sum runs over count but every running total is $0 + 0 = 0$ . Why this step? We still perform it unconditionally; on all-zero counts it produces all zeros, so no special case for empty input is needed.
Placement loop over reversed([]) runs zero times. out = [None]*0 = []. Result: $[]$ .

Singleton case, $A = [5]$ , $k = 5$ :

Tally: count=[0,0,0,0,0,1].
Prefix sum: count=[0,0,0,0,0,1]. Why this step? count[5]=1 says "one key is $\leq 5$ ", so value 5 owns slot $0$ — exactly where the lone element must go.
Place: 5: count[5]:1→0, out[0]=5. Result: $[5]$ .

Verify: empty → empty (length 0); singleton → itself (length 1, value 5). No index error. ✓

Ex 4 — C4: negative keys via min-offset

Worked example Sort

$A = [- 3, 1, - 1, - 3, 2]$ . Forecast: array indices can't be negative, so we must shift. Guess the offset.

Step 1 — Find the shift. $min = - 3$ . Define index $= v - min = v + 3$ . Shifted keys: $[- 3 + 3, 1 + 3, - 1 + 3, - 3 + 3, 2 + 3] = [0, 4, 2, 0, 5]$ . New range $[0, max - min] = [0, 2 - (- 3)] = [0, 5]$ , so $k = 5$ . Why this step? Counting sort indexes an array; indices start at 0. Subtracting the minimum maps any contiguous integer range onto $[0, k]$ .

Step 2 — Tally on shifted keys $[0, 4, 2, 0, 5]$ . count size 6: value 0→2, 2→1, 4→1, 5→1. $count = [2, 0, 1, 0, 1, 1]$

Step 3 — Prefix sum. $count = [2, 2, 3, 3, 4, 5]$ Why this step? Now count[v] = number of shifted keys $\leq v$ , giving the block boundaries. e.g. count[0]=2 → the two 0's own slots $0, 1$ ; count[5]=5 → value 5 owns slot $4$ .

Step 4 — Place shifted keys (right→left of the original order).

5: count[5]:5→4, out[4]=5
0: count[0]:2→1, out[1]=0
2: count[2]:3→2, out[2]=2
4: count[4]:4→3, out[3]=4
0: count[0]:1→0, out[0]=0

Why this step (and right→left)? Each shifted key claims its highest free slot from the prefix-sum boundary, walking down; scanning the original array from the back keeps equal keys stable.

Shifted sorted: $[0, 0, 2, 4, 5]$ .

Step 5 — Un-shift (add back $min = - 3$ ): $[0 - 3, 0 - 3, 2 - 3, 4 - 3, 5 - 3] = [- 3, - 3, - 1, 1, 2]$

Verify: equals sorted([-3,1,-1,-3,2]). Multiset preserved: two $- 3$ , one each of $- 1, 1, 2$ . ✓

Ex 5 — C5: sparse range, $k ≫ n$ (limiting behaviour)

Worked example Sort

$A = [0, 1000, 5]$ , $k = 1000$ . Forecast: only 3 elements, but the count array has 1001 cells — almost all empty. Watch the waste.

Step 1 — Tally. count size 1001, zeros except: count[0]=1, count[5]=1, count[1000]=1. All other 998 cells stay 0. Why note this? The prefix-sum step must still walk all 1001 cells — that's the $O (k)$ term dominating $O (n) = O (3)$ .

Step 2 — Prefix sum. After running totals: count[0..4]=1, count[5..999]=2, count[1000]=3.

Step 3 — Place (right→left).

5: count[5]:2→1, out[1]=5
1000: count[1000]:3→2, out[2]=1000
0: count[0]:1→0, out[0]=0

Result: $[0, 5, 1000]$ .

Verify: sorted correctly. But the runtime cost $\approx k = 1000 ≫ n = 3$ . This is exactly the "counting sort is NOT always faster" trap — with $k ≫ n$ you pay $O (k)$ for nearly nothing. A comparison sort ( $3 lo g 3 \approx 5$ ops) crushes it here. ✓

The figure below makes the waste visible: three lonely coral bars (the occupied buckets $0, 5, 1000$ ) surrounded by hundreds of near-empty lavender cells that the prefix-sum pass must nonetheless scan.

The huge empty gap between value 5 and value 1000 is the picture of " $k ≫ n$ ": the $O (k)$ term is all width, no items.

Ex 6 — C6: records + stability

Worked example Sort records by integer key:

$[(2, a), (1, b), (2, c), (1, d), (2, e)]$ , $k = 2$ . Forecast: among the three key-2 records, in what order must $a, c, e$ appear? (Answer: same as input — $a$ then $c$ then $e$ — because counting sort is stable.)

Step 1 — Tally on keys. keys $= [2, 1, 2, 1, 2]$ : value 1→2, 2→3. $count = [0, 2, 3]$

Step 2 — Prefix sum. $count = [0, 2, 5]$ Why? count[1]=2 → key-1 block is slots $0, 1$ ; count[2]=5 → key-2 block is slots $2, 3, 4$ .

Step 3 — Place (right→left — crucial for stability).

$(2, e)$ : count[2]:5→4, out[4]=(2,e)
$(1, d)$ : count[1]:2→1, out[1]=(1,d)
$(2, c)$ : count[2]:4→3, out[3]=(2,c)
$(1, b)$ : count[1]:1→0, out[0]=(1,b)
$(2, a)$ : count[2]:3→2, out[2]=(2,a)

Result: $[(1, b), (1, d), (2, a), (2, c), (2, e)]$ .

Verify: among key 1: $b$ before $d$ (original order ✓). Among key 2: $a, c, e$ in original order ✓. This is stability — the property that lets counting sort be a digit-pass inside Radix Sort. Had we scanned left→right, we'd get $[(1, d), (1, b), (2, e), (2, c), (2, a)]$ — reversed! ✗

Ex 7 — C7: real-world word problem

Worked example

Exam-scores histogram. A class of 8 students scored (out of 5): $[5, 3, 5, 4, 3, 5, 2, 4]$ . The teacher wants them listed lowest→highest, and also wants the count in each grade. Use counting sort. Forecast: grades range 0..5, so $k = 5$ . Guess the sorted list first.

Step 1 — Tally. count size 6. Grades: 2→1, 3→2, 4→2, 5→3. $count = [0, 0, 1, 2, 2, 3]$ Real-world payoff: this tally is the histogram — the teacher already has "one 2, two 3's, two 4's, three 5's" for free.

Step 2 — Prefix sum. $count = [0, 0, 1, 3, 5, 8]$

Step 3 — Place (right→left).

4: count[4]:5→4, out[4]=4
2: count[2]:1→0, out[0]=2
5: count[5]:8→7, out[7]=5
3: count[3]:3→2, out[2]=3
4: count[4]:4→3, out[3]=4
5: count[5]:7→6, out[6]=5
3: count[3]:2→1, out[1]=3
5: count[5]:6→5, out[5]=5

Result: $[2, 3, 3, 4, 4, 5, 5, 5]$ .

Verify: sorted ✓; histogram sums $0 + 0 + 1 + 2 + 2 + 3 = 8 = n$ ✓ (units: students). ✓

Ex 8 — C8: exam twist — sort descending without breaking anything

Worked example Sort

$A = [1, 3, 2, 3, 1]$ into descending order, $k = 3$ , keeping it stable-by-original-order among ties. Forecast: how do you flip the order? Two clean ways — pick one and predict the answer $[3, 3, 2, 1, 1]$ .

Method — reverse-direction (suffix) cumulative sum. In the normal algorithm the cumulative sum counts keys $\leq v$ so the smallest value claims the front slots. To get descending order we instead count keys $\geq v$ , so the largest value claims the front slots. This is the same "running total" idea as a prefix sum, but accumulated from the high end downward — a suffix sum. (The tempting alternative "sort ascending, then reverse" is a trap: reversing swaps the order of equal keys and destroys stability.)

Step 1 — Tally. value 1→2, 2→1, 3→2: $count = [0, 2, 1, 2]$

Step 2 — Suffix cumulative sum (accumulate high→low). Fill each cell with "how many keys are $\geq v$ ", walking indices from the top down: $count [3] = 2, count [2] = 2 + 1 = 3, count [1] = 3 + 2 = 5, count [0] = 5 + 0 = 5$ $count = [5, 5, 3, 2]$ Why this step? Now count[v] = number of keys $\geq v$ = index just past $v$ 's block when large values come first. So value 3 fills slots $0..1$ , value 2 slot $2$ , value 1 slots $3..4$ .

Step 3 — Place (right→left of $A$ for stability).

1: count[1]:5→4, out[4]=1
3: count[3]:2→1, out[1]=3
2: count[2]:3→2, out[2]=2
3: count[3]:1→0, out[0]=3
1: count[1]:4→3, out[3]=1

Result: $[3, 3, 2, 1, 1]$ .

Verify: descending ✓; multiset preserved (two 3's, one 2, two 1's) ✓. Stability among the two 3's: the input has a 3 at pos 2 (0-based index 1) and another at pos 4 (0-based index 3). Scanning right→left we meet the pos-4 3 first — it takes the later slot out[1]; the pos-2 3 comes next and takes the earlier slot out[0]. So the pos-2 (earlier) 3 lands ahead of the pos-4 3 — original order preserved within the descending block. ✓

Recall

Reminder for the questions below: $n$ = number of elements, $k$ = maximum key value (range $[0, k]$ ).

Recall Which scan direction keeps counting sort stable, and why?

Right-to-left over the input, decrementing count[v] before writing ::: The last equal element claims the highest free slot, so equal keys keep original order.

Recall How do you handle negative keys?

Offset by $- min$ so keys map to $[0, max - min]$ , sort, then add $min$ back ::: Array indices start at 0 and can't be negative.

Recall When is counting sort a poor choice (Ex 5)?

When $k ≫ n$ — the $O (k)$ suffix/prefix-sum term dominates and the count array wastes memory ::: See the comparison bound; a $O (n lo g n)$ sort wins.

Recall What is the tally array

also useful for in a word problem (Ex 7)? It is exactly the histogram of value frequencies ::: You get the frequency distribution for free before sorting.

See also: Prefix Sum / Cumulative Array · Bucket Sort · Time Complexity / Big-O