algorithm - Space requirements of a merge-sort

Question

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

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