How it works?

Counting Sort works in two phases: count, then rebuild.

Step-by-Step Process:

1. Count: make a count array where count[v] is how many times the value v appears.
2. Rebuild: walk the values from smallest to largest and write each value v into the output count[v] times.

Example on [4, 2, 2, 8, 3, 3, 1]:

• Count each value: 1 appears once, 2 twice, 3 twice, 4 once, 8 once.
• Rebuild in order: [1, 2, 2, 3, 3, 4, 8].

No comparisons were made: the value itself decided where each element goes.