Comparison vs Non-Comparison Sorting
What is the difference between comparison-based and non-comparison sorting? Learn why one is capped at O(n log n) and the other can reach linear time.
On this page +
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 nine others run step by step, with live pseudocode and comparison counters.
Launch the visualiser Software engineer at a stealth-stage startup, and previously a front-end engineer for around a year and a half.