Counting Sort
Signals to notice
Brute force first
Comparison sort. Doesn't exploit the bounded range. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
The key insight
Count occurrences of each value in a counting array, then reconstruct the sorted output from counts. where k is the range of values. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
What must stay true
If you know every value in [0, k], a count array of size k+1 tells you exactly how many of each value exist. Reconstructing the sorted array from counts is linear. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Easy way to go wrong
Not stable by default — for stability, compute prefix sums of counts and place elements in reverse order of the original array. The fix is usually to return to the meaning of each move, not just the steps themselves.