arrays - 理由 - マージソート 英語

なぜ、mergesortの空間の複雑さはリンクリストのO(log(n))ですか? (2)

配列上のMergesortは空間の複雑さがO（n）であり、リンクされたリスト上のmergesortは空間の複雑さがO（log（n））であり、 ここで文書化されている

私は2つのサブアレイをマージするときに補助記憶装置が必要なので、配列の場合を理解していると思います。 しかし、リンクリストのマージソートでは、2つのサブリンクリストをマージするだけでは問題ありませんか？ 私はこれが新しい頭部を作るために空間の複雑さ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;
}

説明は素晴らしいでしょう。