Counting Sort

Counting sort works when values are integers in a known range $[0, k]$. It counts how many times each value appears, then reconstructs the sorted array.

The idea:

$1.$ Create a count array of size $k+1$, initialized to $0$.

$2.$ For each element, increment its count.

$3.$ Compute prefix sums of counts (cumulative counts).

$4.$ Place each element in its correct position using the counts.

Example for $[4, 2, 2, 8, 3, 3, 1]$ with max $8$:

Counts: $[0, 1, 2, 2, 1, 0, 0, 0, 1]$ Prefix sums tell you where each value ends up. Output: $[1, 2, 2, 3, 3, 4, 8]$

No comparisons are made between input elements.