3

Difference between Auxiliary Space and Space Complexity of Heap Sort?

My attempt:

As explained here:

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.

I googled the space complexity of Heap Sort, I found the space complexity is O(1).

My question is:

Is that explanation correct? What is difference between Auxiliary Space and Space Complexity?

Community
  • 1
  • 1
Display Name is missing
  • 196
  • 2
  • 11
  • 25
  • Whether or not space complexity should include the input **is 100% opinion-based** (and [thus not an appropriate question for Stack Overflow](https://stackoverflow.com/help/closed-questions)). 99.9% of mentions of space complexity I've seen exclude the input, presumably because it doesn't make much sense to include space that's already been allocated before the algorithm even starts. It should be obvious that it makes no sense whatsoever to say an algorithm uses `O(1)` space if you include the `n` elements of the input in that (because `n` elements is not `O(1)`). – Bernhard Barker Jun 01 '17 at 08:25

1 Answers1

9

Auxiliary should be intended as to all the memory that is not used to store the original input.

Heap Sort input is an array of unordered elements and it works by rearranging them in place meaning that no (or a constant amount of it i.e. not depening on the size on the input array) auxiliary space is used (the heap is built using the input array - http://www.algostructure.com/sorting/heapsort.php).

Talking about space complexity you should also take into account the space used by the input and the auxiliary one, so in this sense, the heap sort has space complexity of O(n)+O(1) (n for the input and 1 as auxiliary space). To be fair if you want you could also consider the space used on the stack (recursive implementation of heap sort use that space, though it should be only O(logn), see here for more details).

By the way, auxiliary space of merge-sort can also be O(1) since exists a version of merge-sort which sorts the array in place (How to sort in-place using the merge sort algorithm?).

Davide Spataro
  • 7,319
  • 1
  • 24
  • 36