Space requirements of a merge-sort

Posted by Arkaitz Jimenez on Stack Overflow See other posts from Stack Overflow or by Arkaitz Jimenez
Published on 2010-06-03T15:00:56Z Indexed on 2010/06/03 15:04 UTC
Read the original article Hit count: 237

Filed under:
|
|

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

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about sorting