title: Merge sort time and space complexity
body: <p>Let's take this implementation of Merge Sort as an example</p>
  <pre><code>void mergesort(Item a[], int l, int r) {
  if (r &lt;= l) return;
  int m = (r+l)/2;
  mergesort(a, l, m);   ------------(1)
  mergesort(a, m+1, r); ------------(2)
  merge(a, l, m, r);
  </code></pre>
  <p>a) The time complexity of this Merge Sort is <code>O(n lg(n))</code>. Will parallelizing (1) and (2) give any practical gain? Theorotically, it appears that after parallelizing them also you would end up in <code>O(n lg(n))</code>. But practically can we get any gains?</p>
  <p>b) Space complexity of this Merge Sort here is <code>O(n)</code>. However, if I choose to perform in-place merge sort using linked lists (not sure if it can be done with arrays reasonably) will the space complexity become <code>O(lg(n))</code>, since you have to account for recursion stack frame size?
  Can we treat <code>O(lg(n))</code> as constant since it cannot be more than 64? I may have misunderstood this at couple of places. What exactly is the significance of 64?</p>
  <p>c) <a href="http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html" rel="noreferrer">Sorting Algorithms Compared - Cprogramming.com</a> says merge sort requires constant space using linked lists. How? Did they treat <code>O(lg(n))</code> constant?</p>
  <p>d) <em>Added to get more clarity.</em> For space complexity calculation is it fair to assume the input array or list is already in memory? When I do complexity calculations I always calculate the &quot;Extra&quot; space I will be needing besides the space already taken by input. Otherwise space complexity will always be <code>O(n)</code> or worse.</p>