Counting sort for it to k d0C[d←0 for i<I to n do calil<-ClAlill+1 bcli- lkey=i for it2 to k do c[i<Ci+ Cli-l b Cli- key si forj←- n downto l doBC[4j←A[ C[A[小←C[A[-1 o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.12© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.12 Counting sort for i ← 1 to k do C[i] ← 0 for j ← 1 to n do C[A[ j]] ← C[A[ j]] + 1 ⊳ C[i] = |{key = i}| for i ← 2 to k do C[i] ← C[i] + C[i–1] ⊳ C[i] = |{key ≤ i}| for j ← n downto 1 do B[C[A[ j]]] ← A[ j] C[A[ j]] ← C[A[ j]] – 1