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

Here $n=500$ (number of items) and $k=100$ (largest possible key). Counting sort is $O(n+k)=O(500+100)=O(600)$ operations — effectively linear. Since $k=100$ is smaller than $n=500$, the range is tiny relative to the data. Yes, excellent fit. The count array needs size $k+1=101$. Trivial memory.

• (a) $n=10^6$, $k=9$: great — $O(n+k)\approx O(10^6)$.
• (b) $n=50$, $k\approx 4.29\times 10^9$: terrible — you'd allocate ~4.3 billion cells to sort 50 numbers. Time and space blow up to $O(k)$.
• (c) $n=10^4$, $k=120$: great — $O(10^4+120)$. Rule: counting sort wins only when $k=O(n)$. Case (b) has $k\gg n$.

Tally (count[0..4]): values seen — one $0$, three $1$'s, one $3$, two $4$'s. $\text{count}=[1,3,0,1,2]$ Prefix sum (each cell = itself + previous): $1,1+3=4,4+0=4,4+1=5,5+2=7$. $\text{count}=[1,4,4,5,7]$ Read as "# of keys $\le v$": $\le 0$ is $1$, $\le 1$ is $4$, $\le 3$ is $5$, $\le 4$ is $7$ (all of them ✓). Place, scanning $A$ right→left ($v$ = key, do count[v]-=1 then out[count[v]]=v):

• $1$: count[1]=4→3, out[3]=1
• $4$: count[4]=7→6, out[6]=4
• $0$: count[0]=1→0, out[0]=0
• $1$: count[1]=3→2, out[2]=1
• $3$: count[3]=5→4, out[4]=3
• $1$: count[1]=2→1, out[1]=1
• $4$: count[4]=6→5, out[5]=4 Result: $[0,1,1,1,3,4,4]$. ✓

Keys aren't in $[0,k]$: the minimum is $\min =-3$. Offset every key by $-\min =+3$, so index $=v-(-3)=v+3$. Shifted keys: $[-3+3,1+3,-3+3,0+3,2+3]=[0,4,0,3,5]$. Range is $[0,5]$, so $k=5$, count size $6$. Tally: $[2,0,0,1,1,1]$. Prefix: $[2,2,2,3,4,5]$. Sort the shifted keys → $[0,0,3,4,5]$. Un-shift (subtract $3$): $[-3,-3,0,1,2]$. ✓

Tally: one key-$0$, two key-$1$ → count=[1,2]. Prefix: count=[1,3]. Now scan left→right (count[v]-=1 then out[count[v]]=x):

• $(1{,}^{\prime }{a}^{\prime })$: count[1]=3→2, out[2]=(1,'a')
• $(1{,}^{\prime }{b}^{\prime })$: count[1]=2→1, out[1]=(1,'b')
• $(0{,}^{\prime }{c}^{\prime })$: count[0]=1→0, out[0]=(0,'c') Result: $[(0{,}^{\prime }{c}^{\prime }),(1{,}^{\prime }{b}^{\prime }),(1{,}^{\prime }{a}^{\prime })]$. The keys are sorted ($0,1,1$) — so the bug is invisible on plain numbers. But among the equal 1's, the original order was a then b; the output has b then a. Stability is destroyed. Right-to-left placement would have kept a before b.

Cost $=O(n+k)=O(10^4+10^8)=O(10^8)$ — dominated entirely by $k$. It is not linear in $n$; you allocate ~$10^8$ cells to sort $10^4$ items. Here $k=10^8\gg n=10^4$, so counting sort degrades badly (compare to $n{\log }_{2}n\approx 10^4\cdot 13.3\approx 1.3\times 10^5$ for a comparison sort — over 700× less work). Use a comparison sort, or Radix Sort which breaks each large key into small-radix digits and runs counting sort per digit, keeping each pass's $k$ small.

Write each as two digits: $32,15,03,41,25$. Pass 1 — ones digit (keys $2,5,3,1,5$). Stable counting sort by ones: Tally at digits $1,2,3,5,5$: count[1]=1, [2]=1, [3]=1, [5]=2. Ordering by ones digit (stable): $41(1),32(2),03(3),15(5),25(5)$ → $[41,32,3,15,25]$. (The two 5's, $15$ then $25$, keep their input order — stability.) Pass 2 — tens digit (of $[41,32,03,15,25]$, tens digits $4,3,0,1,2$). Stable counting sort by tens: $03(0),15(1),25(2),32(3),41(4)$ → $[3,15,25,32,41]$. Final: $[3,15,25,32,41]$. ✓ Fully sorted — and stability in each pass is what let earlier-digit order survive.

Use key(x) to read the integer, but write the whole record: out[count[v]] = x. Tally on keys $2,0,2,1$: count=[1,1,2]. Prefix: count=[1,2,4]. Place right→left:

• $(1,"w")$: count[1]=2→1, out[1]=(1,"w")
• $(2,"z")$: count[2]=4→3, out[3]=(2,"z")
• $(0,"y")$: count[0]=1→0, out[0]=(0,"y")
• $(2,"x")$: count[2]=3→2, out[2]=(2,"x") Result: $[(0,"y"),(1,"w"),(2,"x"),(2,"z")]$. Among key-$2$ records, $"x"$ (input-first) precedes $"z"$ — stable copy confirmed. See Stability in Sorting.

Let $c_v$ = count of value $v$, and $L(v)=\#\{\text{keys}<v\}={\sum }_{i<v}{c}_i$. After prefix sum, count[v] $={\sum }_{i\le v}{c}_i=L(v)+c_v$. During placement, the first time we meet a $v$ we write at count[v]-1 $=L(v)+c_v-1$; each subsequent $v$ decrements, so we write at indices $L(v)+c_v-1,L(v)+c_v-2,\dots ,L(v),$ exactly $c_v$ slots — the contiguous block $[L(v),L(v)+c_v-1]$. No overlap: the next value $v+1$ starts at $L(v+1)=L(v)+c_v$, which is exactly one past $v$'s last slot. So block of $v$ ends at $L(v)+c_v-1$ and block of $v+1$ begins at $L(v)+c_v$. Adjacent, never overlapping. Every index $\mathrm{0..}n-1$ is covered once. ∎ Check on $A=[2,0,2,3]$: counts $c_0=1,c_1=0,c_2=2,c_3=1$. $L(0)=0,L(2)=1,L(3)=3$. Blocks: $0\to [0,0]$, $2\to [1,2]$, $3\to [3,3]$. Prefix count=[1,1,3,4]. Sorted output $[0,2,2,3]$ — index $0$ holds $0$, indices $1,2$ hold $2$'s, index $3$ holds $3$. Matches the blocks exactly. ✓

The $\Omega (n\log n)$ bound applies only to comparison-based sorts — algorithms whose only way to learn about the data is asking "is $a<b$?". A binary decision tree of comparisons must have at least $n!$ leaves (one per possible ordering), so its depth is $\ge {\log }_2(n!)\approx n{\log }_{2}n$. Counting sort never asks that question. It uses the key itself as an array index — reading "value $7$ → bucket $7$" is an $O(1)$ random-access operation, not a comparison. The decision-tree model simply doesn't describe it, so its lower bound doesn't apply. The assumption exploited: keys are integers in a small known range $[0,k]$ that can serve directly as array indices. Remove that (arbitrary floats, huge $k$, strings without a small-integer mapping) and you're forced back to comparisons — and the $\Omega (n\log n)$ wall returns. See Time Complexity / Big-O.