I can not see why the heapsort is considered an inplace sorting algorithm.
I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the extraction of the min value and the sorting process.
So may be I am misunderstanding the definition of inplace here?
But insertion sort for example it is obvious that it is inplace algorith, i.e. no extra memory needed for the elements.
So why is it considered inplace?
Best Answer
No. The array is transformed to conform to the heap constraint without using more than O(1) extra memory. (In fact all you need is extra memory sufficient to hold one element of the array, for swap purposes, plus a boolean or two and a loop variable or two).
Ok, on a technicality it may be that heapsort is usually explained as using a separate heap, but it's perfectly possible to implement it in-place.