New answers tagged

0

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. $$


0

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.


Top 50 recent answers are included