Two families of sorting
Sorting algorithms split into two families based on how they decide order. Comparison sorts order elements only by asking whether one is less than another. Non comparison sorts use the structure of the keys themselves, such as their digits or values.
The comparison sort limit
Any sort that relies purely on comparisons has a proven lower bound on the number of comparisons it must make in the worst case.
- This is because each comparison gives only one bit of information, and there are many possible orderings to distinguish.
- Merge sort, heapsort, and quicksort are all comparison sorts and cannot beat this barrier in general.
How non comparison sorts escape it
- Counting sort tallies how many times each key value appears, then writes elements out in order.
- Radix sort sorts by digits from least to most significant, using a stable counting pass per digit.
- Bucket sort distributes elements into ranges, sorts each, and concatenates.
These avoid the comparison limit by reading key contents directly, but they require keys with bounded range or known structure.
The tradeoff
Non comparison sorts can be very fast on integers or fixed length keys, yet they need extra memory and assumptions that general comparison sorts do not.
Key idea
Comparison sorts order by pairwise comparison and face a fundamental lower bound, while non comparison sorts like counting and radix read key structure to go faster, at the cost of extra memory and assumptions on the keys.