If we know the range of our numbers (e.g., 0-9), we don't need to compare them. We can just count how many times each number appears.
Found a 4. Increment the counter at index 4.
Found a 2. Increment index 2.
Another 2! Increment index 2 to 2.
Found an 8.
Found a 3.
Another 3.
Found a 1. Counting phase complete!
Index 0 has count 0. Nothing to add.
Index 1 has count 1. Add one '1' to the output.
Index 2 has count 2. Add a '2'.
Still have one '2' left. Add it.
Index 3 has count 2. Add '3'.
Add another '3'.
Index 4 has count 1. Add '4'.
Counts are zero. Skip.
Index 8 has count 1. Add '8'.
We reconstructed the sorted array just by counting frequencies. No comparisons were made.
O(n + k). If the range (k) is small, this is faster than any comparison sort. If k is huge (e.g., 1 billion), this is terrible.
Counting Sort is the simplest non-comparison sort, ideal for small ranges.