Step 4 of 6

Counting sort

Comparison sorts can't beat O(n log n). But when the values are small integers in a known range 0..k, you don't need comparisons at all: count how many times each value occurs, then write them back in order. That's O(n + k).

It's the core of radix sort, and it's why sorting a million ages or exam scores is basically instant.

Your turn: write void counting_sort(std::vector<int>& v, int max_value) for values in 0..max_value.

Previous: Quicksort and partitioning Next: Stability and custom comparators