arrays - quick - ordenamiento por mezcla java

¿Por qué la complejidad del espacio mergesort O(log(n)) con listas enlazadas?

Question

Mergesort en una matriz tiene una complejidad espacial de O (n), mientras que mergesort en una lista enlazada tiene una complejidad espacial de O (log (n)), documentada aquí

Creo que entiendo el caso de matriz, porque necesitamos almacenamiento auxiliar al fusionar las dos sub-matrices. Pero, ¿no combinaría una lista enlazada, simplemente fusionaría las dos listas sub vinculadas? Creo que esto tendría una complejidad de espacio O (1) para crear una nueva cabeza.

Fusión en el lugar (sin almacenamiento auxiliar):

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;
}

Una explicación sería genial.

Answer 1

El algoritmo de mergesort es recursivo, por lo que requiere un espacio de pila O (log n), tanto para la matriz como para los casos de la lista vinculada. Pero el caso de matriz también asigna un espacio O (n) adicional, que domina el espacio O (log n) requerido para la pila. Entonces la versión del arreglo es O (n), y la versión de la lista enlazada es O (log n).

Answer 2

Mergesort es un algoritmo recursivo. Cada paso recursivo pone otro marco en la pila. Ordenar 64 elementos tomará un paso recursivo más que 32 elementos, y de hecho es el tamaño de la pila al que se hace referencia cuando se dice que el requisito de espacio es O (log (n)).