27

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.

modulitos
  • 14,737
  • 16
  • 67
  • 110

2 Answers2

30

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).

Jim Lewis
  • 43,505
  • 7
  • 82
  • 96
  • Why O(n) dominates O(logn)? I though merge sort will have n + log(n) complexity when using array? n -> subarray and log(n) call stack? – nhoxbypass Jan 31 '18 at 03:56
  • 5
    @nhoxbypass O(n + log n) is still O(n) because we drop lower order terms. – David G Jul 21 '18 at 12:58
23

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)).

dcsohl
  • 7,186
  • 1
  • 26
  • 44
  • 2
    Alternatively, you can use the iterative version that needs only a constant number of integers and pointers, but you need `O(log n)` bits to represent an integer or pointer. – tmyklebu Jun 11 '14 at 20:07
  • @tmyklebu: You're confusing two separate things. You can either choose to model 1 integer in the range 0..n-1 as taking O(1) space (the usual approach), or as taking O(log n) space; if you choose the latter (which you seem to be doing), then recursive mergesort takes O(log^2(n)) space (O(log n) stack levels, each of which requires at least 2 pointers of O(log n) bits each). I suspect the O(n log n) space complexity for linked lists is because the iterative version can't be implemented in O(n log n) time with only O(1) pointers as it requires O(1) strided accesses for arbitrary stride sizes. – j_random_hacker Jun 12 '14 at 03:41
  • @j_random_hacker: Strided accesses are no problem; after every seek of length k, you access 2k consecutive elements. My point was that there are two very different ways to arrive at the O(log n) space bound given depending on the assumptions you make about your computer. – tmyklebu Jun 12 '14 at 04:24
  • @tmyklebu: I follow your first sentence, but that has only persuaded me that linked lists can be mergesorted in O(n log n) time and O(1) extra space, and that the claim on the page the OP links to is therefore wrong! Your second sentence (and your original comment) is still at best very misleading, as it suggests equivalence between the space usage of the iterative and recursive forms of mergesort on linked lists, when (as you have just shown!) the former is strictly better if we compare apples with apples. – j_random_hacker Jun 12 '14 at 05:08
  • @j_random_hacker: Yes, I agree that it's misleading. I don't know a better way to point out the subtlety, though. – tmyklebu Jun 12 '14 at 05:20
  • @tmyklebu: OK, glad we're on the same page now :) I'd just have added something like " -- though note that under this computational model, the space complexity for the recursive form increases to O(log^2(n))". – j_random_hacker Jun 12 '14 at 05:35
  • So merge sort will have n + log(n) complexity when using array? n -> subarray and log(n) call stack? – nhoxbypass Jan 31 '18 at 03:53