Почему сложность объединенных пространств O (log (n)) со связанными списками?

Mergesort на массиве имеет пространственную сложность O (n), в то время как mergesort в связанном списке имеет пространственную сложность 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;
}

Объяснение будет большим.

Ответы

Ответ 1

Mergesort - это рекурсивный алгоритм. Каждый рекурсивный шаг помещает в стек другой кадр. Сортировка 64 элементов займет еще один рекурсивный шаг, чем 32 элемента, и на самом деле это размер стека, на который ссылается, когда требование пространства указано как O (log (n)).

Ответ 2

Алгоритм mergesort является рекурсивным, поэтому для стека O (log n) требуется пространство стека как для массива, так и для связанных списков. Но случай массива также выделяет дополнительное пространство O (n), которое доминирует над пространством O (log n), необходимым для стека. Таким образом, версия массива - O (n), а версия связанного списка - O (log n).