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.
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 ];
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 requires
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.