Counting sort works when values are integers in a known range . It counts how many times each value appears, then reconstructs the sorted array.
The idea:
Create a count array of size , initialized to .
For each element, increment its count.
Compute prefix sums of counts (cumulative counts).
Place each element in its correct position using the counts.
Example for with max :
Counts: Prefix sums tell you where each value ends up. Output:
No comparisons are made between input elements.