Instead of comparing elements, count how many times each value occurs. Running totals of those counts tell you exactly where each value belongs in the output.
- Average time
- O(n + k)
- Space
- O(n + k)
Instead of comparing elements, count how many times each value occurs. Running totals of those counts tell you exactly where each value belongs in the output.