Space requirements of a merge-sort
- by Arkaitz Jimenez
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
