arrays - 为什么合并排序空间复杂度 O(log(n)) 与链表？

Question

数组上的归并排序具有 O(n) 的空间复杂度，而链表上的归并排序具有 O(log(n)) 的空间复杂度，已记录 here

我相信我理解数组的情况，因为我们在合并两个子数组时需要辅助存储。但是，链表合并排序不会就地合并两个子链表吗？我认为创建新头部的空间复杂度为 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;
}

最好有解释。

Answer 1

归并排序算法是递归的，因此对于数组和链表情况，它需要 O(log n) 堆栈空间。但是数组的情况还分配了一个额外的 O(n) 空间，它支配了堆栈所需的 O(log n) 空间。所以数组版本是O(n)，链表版本是O(log n)。