1

I was wondering if someone could explain to me how the space complexity of both these algorithms work. I have done readings on it but they seem to be contradictive, if I understand correctly.

I'm for example interested in how a linked list would affect the space complexity and this question says it makes it faster?; Why is mergesort space complexity O(log(n)) with linked lists?

This question however says it shouldn't matter; Merge Sort Time and Space Complexity

Now I'm a bit new to programming and would like to understand the theory a bit better so dummie language would be appreciated.

DarthRubik
  • 3,927
  • 1
  • 18
  • 54
Ajay
  • 1
  • 3

2 Answers2

2

The total space complexity of merge sort is O(n) since you have to store the elements somewhere. Nevertheless, there can indeed be a difference in additional space complexity, between an array implementation and a linked-list implementation.

Note that you can implement an iterative version that only requires O(1) additional space. However, if I remember correclty, this version would perform horribly.

In the conventional recursive version, you need to account for the stack frames. That alone gives a O(log n) additional space requirement.

In a linked-list implementation, you can perform merges in-place without any auxiliary memory. Hence the O(log n) additional space complexity.

In an array implementation, merges require auxiliary memory (likely an auxiliary array), and the last merge requires the same amount of memory as that used to store the elements in the first place. Hence the O(n) additional space complexity.

Keep in mind that space complexity tells you how the space needs of the algorithm grows as the input size grows. There are details that space complexity ignores. Namely, the sizes of a stack frame and an element are probably different, and a linked-list takes up more space than an array because of the links (the references). That last detail is important for small elements, since the additional space requirement of the array implementation is likely less than the additional space taken by the links of the linked-list implementation.

Nelfeal
  • 12,593
  • 1
  • 20
  • 39
  • Note that a recursive in place merge sort for an array or vector only requires O(log(n)) stack space, with time complexity O(n log(n)), with a constant factor making it about 3 times as slow as a standard merge sort (2.7 times slower based on a few benchmarks I ran). – rcgldr Mar 17 '18 at 20:03
0

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

This is only true for top down merge sort for linked lists, where O(log2(n)) stack space is used due to recursion. For bottom up merge sort for linked lists, space complexity is O(1) (constant space). One example of an optimized bottom up merge sort for a linked list uses a small (26 to 32) array of pointers or references to to the first nodes of list. This would still be considered O(1) space complexity. Link to pseudo code in wiki article:

https://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

rcgldr
  • 27,407
  • 3
  • 36
  • 61