Merge sort
Split the list in half, sort each half the same way, and then walk the two sorted halves together taking the smaller front element each time. The splitting stops at runs of one, which are sorted already, so there are ⌈log₂ n⌉ levels of splitting and each level merges a total of n elements. That gives n log n, and it gives it on every input: unlike quicksort there is no arrangement that makes the split uneven. The curve plots comparisons, which is what every textbook bound for a sort is about and what makes the four of them directly comparable. The moves are counted too and shown in the panel beside it — worth a look on merge sort, whose comparison count hides the fact that it touches every element on every level.
The claim being tested
O(n log n)
When it is the right choice
When the worst case matters, when the sort has to be stable, or when the data does not fit in memory — merge sort is the basis of every external sort, because merging two sorted streams needs only one element of each in memory at a time. Its cost is the scratch space: O(n) extra, which is why an in-place quicksort is usually preferred when the worst case can be ruled out.
How it works
- If the list has fewer than two elements it is already sorted; stop.
- Split it in half and sort each half the same way.
- Walk the two sorted halves together, taking the smaller front element each time.
- Copy the merged run back over the original range.
- Count one comparison per merge step and one move per element copied back.
Worth noticing
- On log-log axes this is *nearly* straight, with a gradient just above 1 that drifts downwards as n grows — 1.56 from 8 to 16, and 1.10 from 32,768 to 65,536. That is what n log n looks like measured: not a power law, so it has no single exponent, and the drift is the log factor being slowly outgrown by the n.
- The three shapes give almost the same count, and where they differ it is small and in the expected direction: already-sorted input lets every merge exhaust one side early, which saves comparisons and no moves at all.
- The whole fit is within 2.6 per cent, which is as close as any bound here gets without being exact. The one it is fitted against — n log₂n − n + 1 — is the exact worst case for a top-down merge sort, and the gap is the merges that exhaust one side early and save a comparison.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Extra space
- O(n)
- n is
- the length of a list of numbers
- Measures
- shuffled: up to n = 131,072; sorted: up to n = 131,072; reversed: up to n = 131,072
The ceilings are a time limit rather than a memory one, which makes this tool the odd one out in the suite. Its recorded steps are tiny — one step per measured size, not one per operation — so nothing about the trace would ever stop a run. What has to be stopped is the measuring itself: a configuration that would take more than forty million operations to count is refused before a single one of them is counted, from a formula in the input sizes rather than by starting and giving up. Two further limits sit beside it that no formula in operations can see: building the input is real work, and a recursion n deep overflows the call stack long before its operation count becomes interesting.
A fit over a dozen sizes is evidence and not proof. It cannot rule out a term that only begins to matter past the largest size measured, and it says nothing at all about the constant factors that decide which of two algorithms in the same class is actually faster on a real machine.