Counting Sort

Counting sort uses some assumptions:

• Assume the input array contains $n$ non-negative integers.
• Assume that each element $a \in A$ is in the range 0 to $k$, for some integer $k$.

Example

Suppose $A = [1, 3, 4, 0, 2, 2, 3]$. This implies that $k \geq 4$, where the most efficient choice of $k$ is 4.

We work with 3 arrays:

• An input array A
• An output array B
• A temporary array C

We initialize $C$ to be of length $k$. We begin the algorithm by counting the number of elements for all $i \in \{0, 1, \dots, k\}$. We assign each $C[i]$ to be the number of times that $i$ appears in $A$.