All four methods below sort the list correctly. On twenty items you would not notice the difference. On a million, one of them finishes while you blink and another would still be running next week — not because the computer changed, but because of how the work grows with the size of the problem. That growth rate is the single most useful thing to know about any piece of code.
Each panel is running a different algorithm on an identical copy of the data. The number beside each name is how many comparisons it has made so far — the honest measure of work, because it does not depend on how fast the machine is. Watch the two on the right finish long before the two on the left, then try nearly sorted and watch insertion sort win outright.
Here the same four are run to completion at every size, and the comparisons counted. Both axes are logarithmic, so a straight line is a power law and its steepness is the exponent. The quadratic pair climb twice as steeply as the others. That is not a small constant factor you could optimise away — it is a different shape, and at some size it always wins.
| items | bubble | insertion | merge | quick | merge is faster by |
|---|
Looking for one name in a sorted list of a million: check them one at a time and you may need a million looks. Cut the list in half each time and you need twenty. Every doubling of the data adds exactly one step — which is why a database index is worth building and why the phone book worked.
Sorting got easier because someone found a cleverer method. For other problems nobody has, and there are reasons to think nobody will. Finding the shortest route through a set of cities by checking every route means (n−1)!/2 possibilities — a number that outruns any computer almost immediately. Twenty cities is already sixty quadrillion routes.
Every number on this page comes from actually running the algorithm and incrementing a counter on each step, not from plotting a formula. Bubble sort lands on n²/2 — 523,776 for 1,024 items against a predicted 524,288 — and insertion sort on about half that, because on random data it stops each scan as soon as the item is in place. Merge sort comes out at exactly 10,240, which is 1,024 × log₂1,024 to the digit: it touches every element once per level and there are log₂n levels, so the count is forced. One caveat on reading these against a textbook: what is counted here is steps taken, which for merge sort means elements placed rather than comparisons made. The two differ by a small constant and not by shape.
Two honest caveats. Comparison counts ignore what each comparison costs, and on real hardware an algorithm that touches memory in order can beat one that does fewer operations but scatters them — which is exactly why the sort in your language's standard library is a hybrid rather than the textbook merge sort. And quicksort's reputation for speed comes with a worst case of n² when the pivot is chosen badly; the version here picks the middle element, which is enough to make the sorted-input case behave.