Answers · Making it fast enough

Why is merge sort O(n log n) when it keeps splitting the array in half?

In shortSplitting in half gives about twenty levels for a million items, and merging at every level still touches all million items, so the total is twenty million rather than a million times a million.

Merge sort is $O(n\log n)$ because halving the array gives $\log_2 n$ levels, and the merging at each level touches all $n$ items once. For a million items that is about twenty levels of one million units each, so about twenty million units, not a million levels of a million items.

\frac{n}{2^k}=1 \quad\Longrightarrow\quad 2^k=n \quad\Longrightarrow\quad k=\log_2 n

For $n=8$ the sequence is 8, 4, 2, 1: three halvings because $2^3=8$ . For $n=16$ it is four halvings because $2^4=16$ . The number of halvings is the exponent that must be put on 2 to get $n$ , and that is what $\log_2 n$ means.

Start with $n=1{,}000{,}000$ . After one split there are 2 pieces of 500,000. After two splits there are 4 pieces of 250,000. After three splits there are 8 pieces of 125,000. The piece size after $j$ splits is $1{,}000{,}000/2^j$ , and it reaches 1 when $2^j=1{,}000{,}000$ . That is between 19 and 20, because $2^{19}=524{,}288$ and $2^{20}=1{,}048{,}576$ . So the recursion has about 20 levels, not a million.

The work that matters is merging, not the act of splitting. At the top level one merge combines two halves of 500,000 and costs about 1,000,000 units. At the next level two merges of 250,000 each cost 500,000 each, which is 1,000,000 in total. At the next four merges of 125,000 cost 125,000 each, which is again 1,000,000. At the bottom there are 500,000 merges of pairs of single items; each costs 2 units, so the level still costs 1,000,000. The pieces shrink as fast as they multiply, so the level cost stays put.

2^j \times \frac{n}{2^j}=n

Write the level as $j$ . At level $j$ there are $2^j$ pieces of size $n/2^j$ , so the cost of that level is $2^j \times n/2^j = n$ . There are $k$ such levels, where $k=\log_2 n$ , so the sum is $n$ added to itself $k$ times.

FIG 1

merges at level	size of each merged piece	cost of each merge	cost of level
1	1048576	1048576	1048576
2	524288	524288	1048576
4	262144	262144	1048576
524288	2	2	1048576

The natural guess is that because each half is half the size, the work should fall away, or that the number of levels is the number of items. Neither happens. The number of pieces doubles exactly as the size of each piece halves, so the two effects cancel at every level. The depth is not $n$ . It is the number of times $n$ can be halved before reaching 1, which is $\log_2 n$ . If the depth were $n$ , the total would be $n^2$ . If the per-level cost fell, the total would be less than $n\log n$ . The cancellation is the whole reason the total is $n\log n$ rather than either of those.

So the total is the cost of one level multiplied by the number of levels: $n \times \log_2 n$ . For the exact case $n=1{,}048{,}576=2^{20}$ , there are 20 levels and the total is $20 \times 1{,}048{,}576 = 20{,}971{,}520$ units. For a million items it is about $20 \times 1{,}000{,}000 = 20{,}000{,}000$ units. If there were a million levels, the total would be $1{,}000{,}000 \times 1{,}000{,}000 = 1{,}000{,}000{,}000{,}000$ units.

This holds only when the two halves can be solved independently and combined cheaply. Sorting passes: two sorted halves merge in one pass by repeatedly taking the smaller front. Finding the largest value passes, but gains only depth, because the combining is one comparison per item either way. Finding the closest pair of points needs care: the closest pair may straddle the dividing line, and the merge must inspect a narrow strip near that line. If combining two halves needs every item of one compared with every item of the other, the merge costs $n^2$ at the top and the method is worse than the loop it replaced.

More generally, if merging a piece of size $m$ costs more than $m$ , the total changes. If it costs $m^2$ , the top level alone costs $n^2$ , and the method is not $O(n\log n)$ at all. The $n\log n$ bound is a statement about one linear pass over the two sorted halves at each level, not about halving on its own.

Worth keeping

Halving an array of n items gives log base 2 of n levels, not n levels.
At every level the number of pieces doubles while each piece halves, so the total merging work at that level stays n.
If two sorted halves cannot be merged in one pass, the n log n total no longer follows.

Where this goes next

This question is one step of Answers Built From Smaller Answers, a course that works through its subject from the beginning. The page that teaches this part of it is Splitting the Work in Half, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course

Why is merge sort O(n log n) when it keeps splitting the array in half?

Worth keeping

Where this goes next

Read alongside