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 Θ(n+k).