CODEWITHSUNDEEP
arraysalgorithmsortinglinked-list
modulitos
modulitos

Reputation: 15814

Why is mergesort space complexity O(log(n)) with linked lists?

Mergesort on an array has space complexity of O(n), while mergesort on a linked list has space complexity of O(log(n)), documented here

I believe that I understand the array case, because we need auxiliary storage when merging the two sub-arrays. But wouldn't a linked list merge sort just merge the two sub-linked lists in place? I think this would have space complexity O(1) for creating a new head.

In place merge (no auxiliary storage):

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

An explanation would be great.

Upvotes: 27

Views: 26485

Answers (2)

Jim Lewis
Jim Lewis

Reputation: 45045

The mergesort algorithm is recursive, so it requires O(log n) stack space, for both the array and linked list cases. But the array case also allocates an additional O(n) space, which dominates the O(log n) space required for the stack. So the array version is O(n), and the linked list version is O(log n).

Upvotes: 31

dcsohl
dcsohl

Reputation: 7406

Mergesort is a recursive algorithm. Each recursive step puts another frame on the stack. Sorting 64 items will take one more recursive step than 32 items, and it is in fact the size of the stack that is referred to when the space requirement is said to be O(log(n)).

Upvotes: 24

Related Questions