Space requirements of a merge-sort

问题:

I'm trying to understand the space requirements for a Mergesort, O(n).
I see that time requirements are basically, amount of levels(logn) * merge(n) so that makes (n log n).
Now, we are still allocating n per level, in 2 different arrays, left and right.
I do understand that the key here is that when the recursive functions return the space gets deallocated, but I'm not seeing it too obvious.
Besides, all the info I find, just states space required is O(n) but don't explain it.
Any hint?

function merge_sort(m)
    if length(m) ≤ 1
        return m
    var list left, right, result
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = merge_sort(left)
    right = merge_sort(right)
    result = merge(left, right)
    return result

EDIT Ok, thanks to @Uri, this is the trick
What I failed to see at the very beginning is that time only adds, while memory adds and subtracts, so the maximum amount of time is at the end of execution, but the maximum amount of memory is at the bottom of the recursive stack.

So, if we keep adding n + n/2 + n/4 + n/8.... it doesn't matter how many times we add, it'll never be bigger than 2n, and when we reach the recursive stack bottom and start going up, we don't keep the memory used for the previous branch, so at max, 2n would be the amount of memory used, O(n).

回答1:

There are versions of merge-sort that can work in place.

However, in most implementations the space is linear in the size of the array. That means n for the first level, n/2 for the second, n/4 for the third, etc. By the time you are at the bottom of your recursion, this series adds up to about 2n, which is linear.

回答2:

This is my explanation for the space complexity for your code. Basically, as the algorithm reaches results how are we doing on memory.

1) Every recursion call you make has a constant size of stack frame allocated as well as any variables that are not a function of "n". Let's call this constanct "c". Since, you are going lg(n) levels deep the result is c*lg(n) which is O(lg(n)).

2) Now, as we compute the result, we allocate space for n/(2^k) elements, where k is the level you are at.

left = merge_sort(left)
right = merge_sort(right)

For folks who may be wondering how we came up with n/(2^k), notice that first we go about allocating memory when solving the first half of the array i.e left=merge_sort(left). Once, this recursion tree is ended, we end up deallocating all memory and come back to starting point before solving for the right side. Hence, its n/(2^k). This is going to be O(n).

3) Finally, merge procedure may allocate extra space too (if using linked list this space may not be needed) which is O(n)

Final answer = O(lg(n)) + O(n) + O(n) which is O(n).