Comparison vs Non-Comparison Sorting
One of the most important distinctions in sorting is whether an algorithm compares elements to each other or exploits the structure of the values directly. This single difference explains why some algorithms are stuck at O(n log n) while others reach linear O(n) time.
Comparison-based sorting
Comparison sorts decide order by asking 'is A less than B?'. Bubble, Selection, Insertion, Merge, Quick, Heap, Shell, and Tim Sort all work this way. Because they only learn about the data through comparisons, they are bound by a hard theoretical limit: no comparison sort can do better than O(n log n) in the worst case.
Non-comparison sorting
Non-comparison sorts never compare two elements directly. Instead they use the values as keys. Counting Sort tallies how many times each value appears and reconstructs the array from those counts in O(n + k) time, where k is the range of values. Radix Sort processes numbers digit by digit in O(nk) time. Because they skip comparisons, they can beat the O(n log n) barrier.
The trade-offs
Linear time sounds like a free win, but non-comparison sorts come with strings attached. They only work on data that can be mapped to integer keys (integers, fixed-length strings), they often need O(k) extra memory, and they become impractical when the value range k is huge. Comparison sorts remain the general-purpose default because they work on any comparable type.
Frequently asked questions
Can any sorting algorithm beat O(n log n)? +
Which sorts are comparison-based? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser