Worst Case Space Complexity of Merge Sort and Bubble Sort

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

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.

StackExchange Computer Science Q#111963, answer score: 4