Why is Merge sort space complexity O(n)?
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 ?
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).