title: Why is mergesort space complexity O(log(n)) with linked lists?
body: <p>Mergesort on an array has space complexity of O(n), while mergesort on a linked list has space complexity of O(log(n)), documented <a href="http://www.sorting-algorithms.com/merge-sort">here</a> </p>
  
  <p>I believe that I understand the array case, because we need auxiliary storage when merging the two sub-arrays. But wouldn't a linked list merge sort just merge the two sub-linked lists in place? I think this would have space complexity O(1) for creating a new head.</p>
  
  <p>In place merge (no auxiliary storage):</p>
  
  <pre><code>public Node merge(Node a, Node b) {
      Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
      while(a !=null &amp;&amp; b!= null) {
          if(a.info &lt;= b.info) { curr.next = a; a = a.next; }
          else { curr.next = b; b = b.next; }
          curr = curr.next;
      }
      curr.next = (a == null) ? b : a;
      return dummyHead.next;
  }
  </code></pre>
  
  <p>An explanation would be great.</p>