Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

Question

I know this is a common algorithm with plenty of analysis, but when I searched for an answer the only one I found was "Merge Sorting has O(n) auxiliary space because it copies the array into L and R".

I don't understand this because as it is called recursively, before performing any operations, the entire array is still split log(n) times. When following the binary tree diagram representing the recursion, we see (if n=16) it splits into 2x8, 4x4, 8x2, 16x1.

Since all of these splits occur prior to any merging, why is the auxiliary space O(n) and not O(nlog(n))?

Answer 1

The $i$-th time the array is split, it is split into into two arrays of size $2^{-i} n$ elements each (assuming, for simplicity, that $n$ was a power of $2$).

At the ($\log n$)-th recursive call, the total space occupied by all these arrays is $$ 2n \sum_{i=1}^{\log n} 2^{-i} \le 2n \sum_{i=1}^{\infty} 2^{-i} = 2n. $$

Answer 2

Yes, you can implement merge sort inefficiently, but you don’t have to.

If you sort an array, notice that you don’t need to create any copies while splitting into subarrays. You only need two integers to identify each of them. Combined with the fact that the number of nodes in the recursion tree is $O(n)$, this gives you $O(n)$ bound on space.