1
$\begingroup$

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))?

$\endgroup$
  • $\begingroup$ How much space does it take to split an array of n items into half? $\endgroup$ – gnasher729 Mar 28 at 7:46
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.