How does merge sort get n log n by splitting and merging?

The $n\log n$ comes from two separate counts multiplied together: the number of halving rounds is $\log_2 n$, and each round merges every item once, which costs $n$. Splitting is only how you arrange the rounds; the work is in the merges.

Take two runs that are already in order, say $2,4,8$ and $1,5,9$. Look only at the two front items. The smaller front item is the smallest item not yet output, because everything behind it in its own run is at least as large. Take it, advance that run's pointer, and repeat. Each comparison places exactly one item, so merging runs with total length $m$ takes at most $m$ placements and at most $m-1$ comparisons. That is linear in $m$, not logarithmic. The final tail of a run is appended without any comparison, which is the only saving and the reason the cost is stated as at most the combined length.

Start with $n$ runs of length 1. After one round there are $n/2$ runs of length 2; after two rounds $n/4$ runs of length 4; after $k$ rounds $n/2^k$ runs of length $2^k$. The merging stops when one run remains, which needs $2^k \ge n$, so $k=\lceil \log_2 n\rceil$. For eight items, $8\to4\to2\to1$ is three rounds. For a million, $2^{19}=524{,}288$ and $2^{20}=1{,}048{,}576$, so the number of rounds is 20.

At a million items the same arithmetic gives 20 rounds and $20 \times 1{,}000{,}000 = 20{,}000{,}000$ item placements. The worst case for comparisons is the same order. Comparing every pair would take $1{,}000{,}000 \times 999{,}999 / 2 = 499{,}999{,}500{,}000$ comparisons, which is about 25,000 times larger. The gap is not a constant improvement; it is the difference between a line and a curve that bends upward.

The usual wrong picture is that splitting costs $\log n$ and merging costs something similar, or that merging two halves is logarithmic because it sounds like binary search. Merging is not searching. A binary search halves one run, but a merge cannot discard half of a run: the smallest remaining item might be at the front of either run, so both fronts must be watched. Watching two fronts and advancing one pointer per output is a single walk over the combined length. The logarithm is purely the number of times you must repeat that linear walk. If you split and then merge by scanning one half for each item of the other, the merge itself becomes quadratic, and the total is no longer $n\log n$.

This is a comparison sort bound. It assumes the only way to learn about an item is to compare it with another. If you can inspect the key, as with digits or small integer ranges, you can sort in linear time per digit or per range and beat $n\log n$ asymptotically. The bound is also asymptotic: at ten items the constants and the cost of allocating half-arrays can dominate, and an insertion sort may be faster. The balanced halving matters too. Splitting at the midpoint gives the log factor; a merge that repeatedly scans from the beginning, or an unbalanced split that leaves one huge piece every time, loses the guarantee. Array merge sort also needs $O(n)$ extra space for the merged output, which is a real cost even when the comparison count is optimal.