Type COUNTING-SORT (CLRS, 1-indexed; reverse placement for stability)

Answer

COUNTING-SORT(A, n, k) let B[1..n], C[0..k] be new arrays for i = 0 to k: C[i] = 0 for j = 1 to n: C[A[j]] = C[A[j]] + 1 for i = 1 to k: C[i] = C[i] + C[i-1] for j = n downto 1 B[C[A[j]]] = A[j] C[A[j]] = C[A[j]] - 1 return B

Count, then prefix-sum so C[i] is the position of the last value-i element, then place right-to-left (downto) — the reverse pass is what makes counting sort stable.