I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(n), linear? All space we need is the exact number of the elements, right? Please enlighten me.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ If you change the merging algorithm a little and working with indexes, you can use just use extra $O(1)$ bit space in merge sort. $\endgroup$– Mohsen GhorbaniCommented Jul 18, 2019 at 16:31
-
$\begingroup$ See also in-place merge sort $\endgroup$– kelalakaCommented Jul 19, 2019 at 11:15
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Typical implementations of Merge sort use a new auxiliary array split into two parts, a left part and a right part. This extra space is the reason for the O(n) space complexity.
During the sort section of the algorithm we have the following two new auxiliary arrays created for additional space.
int leftPartition[] = new int[ leftPartitionSize ];
int rightPartition[] = new int[ rightPartitionSize ];
So, merge sort uses auxiliary arrays to sort. However, quick sort is an in-place sort that uses O(1) space as no auxiliary space is required to sort the data.
Side note: You might also see the space complexity of merge sort as O(nlog(n)). Some would argue that because of the way the recursive calls to merge sort work, the space complexly at any given point is at most O(n). Others might say that adding all the space for all recursive calls requiresO(nlog(n)). The log(n) is because each repeated call to merge sort cuts the existing array in half.
If you want true O(n) complexity, you can pass an auxiliary array as a parameter into the sort method. Therefore, each call to merge sort will use the same array without the need to split the array in half with each call. However, this implementation is quite a bit harder to implement.
