Non-comparison sorts

Beat O(n log n) by NOT comparing — use keys as indices. Counting · radix · bucket. Linear, on bounded integers.

The loophole

• O(n log n) lower bound applies to comparison sorts only
• Counting: tally how many of each value → O(n + k)
• Radix: sort digit by digit (stable) → O(d·(n + b))
• Bucket: scatter into ranges, sort each → O(n) expected

Watch it count, not compare

Each element bumps its bar. No two elements ever compared. Read bars left to right = sorted.

Counting sort beats the library

Counting: 3.3× faster than Timsort on bounded keys. (Radix loses — 7 Python passes.)

The catch: the range k

• Counting sort allocates k counters — wide range = fatal
• Only integers (or keys you can map to integers)
• Bucket sort assumes even distribution
• General data → still a comparison sort

Takeaway

Specialists: linear on bounded integer keys, unbeatable there. The rare case your code beats the library. Next: searching — binary search.