Aux complexity on merge sort modification

Question

According to geekforgeeks:

Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.For example, if we want to compare standard sorting algorithms on the basis of space, then Auxiliary Space would be a better criteria than Space Complexity. Merge Sort uses O(n) auxiliary space, Insertion sort and Heap Sort use O(1) auxiliary space. Space complexity of all these sorting algorithms is O(n) though.

But, assume a scenario, a modification to merge sort, where was to return a brand new sorted array keeping the input array unchanged.

Would the new sorted array which is returned be treated as temporary space ? In other words, would the aux complexity still be O(n) and space be O(n) ?

Answer 1

I've never heard the term auxiliary space complexity. But the regular notion of space complexity separates the input and output space, and the space complexity of your algorithm is any extra space, and for some other more restrictive models to measure space complexity where you can't even write in the input space, it is read only and the output could be written only once, but those are only interesting from a theoretical point of view.

So I guess the output space should not be considered as part of the aux space, I mean you NEED that space, there is no way you may avoid it, that's why in some analysis the running time also uses the output size as parameter.

So yes, the space that you use for the output might not be counted as extra space, nevertheless, in the case of mergesort you can't avoid this O(n) extra space, since you are not touching the input, so you will need another auxiliary array to do the merge step.