title: Space requirements of a merge-sort
body: <p>I'm trying to understand the space requirements for a Mergesort, O(n).<br>
  I see that time requirements are basically, amount of levels(logn) * merge(n) so that makes (n log n).<br>
  Now, we are still allocating n per level, in 2 different arrays, left and right.<br>
  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.<br>
  Besides, all the info I find, just states space required is O(n) but don't explain it.<br>
  Any hint?</p>
  
  <pre><code>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
  </code></pre>
  
  <p><strong>EDIT</strong>
  Ok, thanks to @Uri, this is the trick<br>
  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.  </p>
  
  <p>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).</p>