在数组上执行归并排序的空间复杂度为O(n)，而在链表上执行归并排序的空间复杂度为O(log(n))，详见这里。
我认为我理解了数组的情况，因为在合并两个子数组时需要辅助存储空间。但是链表归并排序不是只需在原地合并两个子链表吗？我认为这将具有O(1)的空间复杂度来创建一个新头。
原地合并（无需辅助存储）：
public Node merge(Node a, Node b) {
Node dummyHead, curr; dummyHead = new Node(); curr = dummyHead;
while(a !=null && b!= null) {
if(a.info <= 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;
}
能够给出一个解释会很好。