Why Merge Sort Costs the Same on Every Input

Merge sort takes O(n log n) time on every input, sorted, reversed or shuffled, because the splits ignore the values and every merge moves all of its items whatever order they arrive in. This card reads that cost off the levels of the recursion, shows why merge sort has no fast best case, and counts the extra memory it needs.

The splits make a tree. The whole array is level 0, its two halves are level 1, their halves level 2, and so on down to pieces of one item. On each level the pieces cover the whole array between them, so the merges on any one level move all n items between them. Halving n until one item is left takes log₂ n steps, so the tree has log₂ n levels that merge, plus the leaves, which do not. An instrumented run of the code on 5 2 7 4 1 8 3 6 counted the items each level merged.

Three levels merge 8 items each, 24 in all, which is n × log₂ n for n = 8. The leaves merge nothing, since a single item is already sorted. That is the recurrence T(n) = 2T(n/2) + O(n) solved by its recursion tree: two calls on halves, linear work outside them, the same total on every level.

The order of the input changes how many comparisons a merge makes, but not how many items it moves. The same instrumented sort on 1,024 items printed the counts below, alongside insertion sort on the sorted input.

Every input moved 10,240 items, which is 1,024 × 10, n log₂ n exactly. Sorted and reversed input halved the comparisons, because in each merge one half runs out after its own items are placed and the rest of the other half is copied without comparing, but halving is a constant factor and the cost is still O(n log n). Insertion sort, by contrast, made 1,023 comparisons on the same sorted input, one per item: it has an O(n) best case because it can see that an item is already in place and stop. Merge sort cannot, because its merge copies every item whether or not it moves, so there is no input on which it finishes early.

The memory has two parts. The buffer the merge copies into holds n items, O(n), and is the reason merge sort on an array is not in place, the term for a sort that uses only O(1) memory beyond the array. The recursion adds one stack frame per level that is open at once, about log₂ n + 1 of them, O(log n), which is small beside the buffer.

Because its cost is the same on every input, merge sort has no bad input for an attacker or an unlucky dataset to find, which makes its running time easy to predict. The trade is the buffer, and a best case no better than its worst.