3

At first look, it makes sense that merge sort has space complexity of O(n) because to sort the unsorted array I'm splitting and creating subarrays but the sum of sizes of all the subarray will be n.

Question : The main concern that I have is that of memeory allocation of mergerSort() function during recurssion. I have a main stack, and each function call to mergerSort() ( recussively) will be pushed on the stack. Now each recussively called mergeSort() function will have its own stack. Therefore, say if we have made 5 recussive calls to mergeSort() then the main stack will contain 5 function call where each function call will have its own function stack. Now each function stack will have its own local varibales like left subarray and right subarray that the function creates. Hence, each of the 5 function stacks should have 5 different subarrays in memeory. So shouldn't the space grow with the growth in recussive calls ?

enter image description here

black sheep 369
  • 564
  • 8
  • 19
  • 2
    If you allocate new sub-arrays in each recursive call, then yes, the total memory usage will be O(n log n). But there is no need to allocate new arrays in MergeSort; it can be done entirely in-place. In that case the only extra space needed is the stack which is O(log n). – Thomas Aug 25 '20 at 10:58
  • @Thomas - there are iterative versions of in place merge sort with total space complexity O(1), which are about 50% slower than merge sorts that use a second array (O(n) space). An example is [grailsort.h](https://github.com/Mrrl/GrailSort/blob/master/GrailSort.h) . – rcgldr Aug 25 '20 at 19:13
  • @rcgldr I don't know what's going on in those 500+ lines of code but it doesn't look like merge sort to me. – Thomas Aug 26 '20 at 10:40
  • @Thomas - that code is the result of numerous optimizations for an "in place" merge sort. Look at the routines for "without buffer". The routines with buffer use a small fixed size buffer to speed things up, which is still O(1) space (since it is a fixed size buffer), but the normal goal is an inplace merge sort that doesn't use any buffer. The binary search is done as part of the merge, find where an element belongs, then "rotate" a sub-array to put the element in place. At the bottom of the code is "classic" in place merge sort. – rcgldr Aug 26 '20 at 20:40

1 Answers1

11

Memory should be linear

Although each call to mergeSort triggers two recursive calls, so it makes sense to talk about and draw the binary tree of recursive calls, only one of those two recursive calls is performed at a time; the first call ends before the second call starts. Hence, at any given time, only one branch of the tree is being explored. The "call stack" represents this branch.

The depth of the recursion tree is at most log(n), therefore the height of the call stack is at most log(n).

How much memory does it take to explore one branch? In other words, how much memory is allocated on the call stack, at most, at any given time?

At the bottom of the call stack, there is an array of size n.

On top of that is an array of size n/2.

On top of that is an array of size n/4.

Etc...

So the total size of the call stack is at most n + n/2 + n/4 + ... < 2n.

Hence the total size of the call stack is at most 2n.

Possible memory leak

If your implementation of merge sort allocates a new array at every recursive call, and you forget to free those arrays at the end of the call, then the total allocated memory becomes the total memory required for the whole tree, instead of just one branch.

Consider all the nodes at a given depth in the tree. The subarrays of these nodes add up to form the whole array. For instance, the root of the tree has an array of length n; then one level below that, there are two subarrays representing two halves of the original array; then one level below that, there are four subarrays representing four fourth of the original array; etc. Hence each level of the tree requires memory n. There are log(n) levels to the tree. Hence the total amount of memory allocated for the whole tree would be n log(n).

Conclusion

If merge sort has no memory leaks, then its space complexity is linear O(n). In addition, it is possible (although not always desirable) to implement merge sort in-place, in which case the space complexity is constant O(1) (all operations are performed directly inside the input array).

However, if your implementation of merge sort has a memory leak, i.e., you keep allocating new arrays in recursive calls, but do not free them when the recursive call returns, then it could easily have space complexity O(n log n).

Stef
  • 13,242
  • 2
  • 17
  • 28