# Counting Sort

## Algorithm (intuitive)

for i = 0 to k-1 do C[i] = 0
for j = 0 to n do C[A[j]] = C[A[j]]+1
t = 0
for i = 0 to k-1 do
for j = 0 to C[i] do
t = t + 1
B[t] = i

## Algorithm (stable)

for i = 0 to k-1 do C[i] = 0
for j = 0 to n do C[A[j]] = C[A[j]]+1
for i = 0 to n do C[i] = C[i-1]+C[i]
for j = n downto 1 do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1

## Complexity

Both are $\Theta (n+k)$.