counting sort
Counting sort throws away comparisons entirely. Instead of asking 'is this bigger than that?', it asks 'how many of each value are there?'. If the keys are small integers in a known range 0..k, you make an array of k+1 counters, sweep the input once tallying how many times each value appears, then walk the counters in order, emitting each value as many times as it was counted. The output comes out sorted without a single element ever being compared to another.
Picture sorting a stack of exam papers scored 0 to 100: make 101 pigeonholes, drop each paper into the hole for its score, then read the holes left to right. To make it stable (preserving the original order of equal keys, which matters when each key carries extra data), you turn the counts into running totals that give each value its block of output positions, then place items by scanning the input from the back.
The cost is O(n + k) time and O(n + k) space, where n is the number of items and k is the size of the value range. When k is comparable to n (small, dense integer keys), this is effectively linear — beating the O(n log n) lower bound that applies to all comparison sorts. There's no contradiction: that lower bound only governs algorithms that learn about order by comparing pairs; counting sort sidesteps it by exploiting the keys' values directly. The catch is the range: if k is huge (e.g. sorting 64-bit integers), the k-sized counter array makes it impractical. It also only works on keys that index an array — integers or things mappable to them, not arbitrary objects.
std::vector<int> countingSort(const std::vector<int>& a, int k) {
std::vector<int> count(k + 1, 0), out;
for (int x : a) ++count[x]; // tally each value
for (int v = 0; v <= k; ++v)
while (count[v]-- > 0) out.push_back(v); // emit in order
return out;
}Before: [2, 5, 2, 0, 3, 0] After: [0, 0, 2, 2, 3, 5] — O(n + k), no comparisons.
The O(n log n) lower bound applies only to comparison sorts (those that sort by comparing pairs of keys). Counting sort, radix sort and bucket sort are non-comparison sorts: they read the keys' actual values, so they can go faster when the keys are restricted (e.g. small integers).