0

I understand that we are constructing a max-heap using the same array (which we have to sort) so there is no extra memory required there (from here).

But my question is what about heapify function (which is recursive when I follow Introduction to Algorithms, CLRS) which we use while building the heap (and also during swapping the first element of heap - that is the biggest and the last element of the heap and then again re-heapifying the array).

The call to this recursive function can, in worst case take O(log(n)) because of storing the stack pointer on each recursive call.

So, my question is that when this wiki article says that heapsort is an inplace sorting algorithm, does it implicitly mean that the heapify function that it is assuming is non-recursive one (which will not take any (non-constant) extra space). Or is there something that I'm missing?

Will the space complexity of heapsort, which uses a recursive heapify function, be O(log(n))?

Lavish Kothari
  • 2,211
  • 21
  • 29
  • 2
    "In-place" just means that it doesn't have to declare an additional array. It doesn't matter if the algorithm has to allocate additional variables or stack frames. – BJ Myers Jan 21 '19 at 17:21
  • 1
    I don't understand your question - why can't a recursive heapify operation update the array in-place? – Lee Jan 21 '19 at 17:21
  • 2
    (log n) / n goes to 0 as n goes to infinity. So the larger n the less the extra space used matters. – Henry Jan 21 '19 at 17:24
  • 1
    @BJMyers [this](https://en.wikipedia.org/wiki/Quicksort#Space_complexity) suggests me that stack frames matter when calculating the space complexity – Lavish Kothari Jan 21 '19 at 17:24
  • @Lee [this](https://en.wikipedia.org/wiki/In-place_algorithm) article says: "Quicksort operates in-place on the data to be sorted. However, quicksort requires O(log n) stack space pointers to keep track of the subarrays in its divide and conquer strategy." so they are technically taking quick sort out of the in-place sorting category. – Lavish Kothari Jan 21 '19 at 17:29
  • 1
    Note how the consideration for Quicksort does not apply to Heapsort. The recursive implementation of Heapsort is not a divide-and-conquer strategy. There is no "divide", ... only "conquer" ;-) – trincot Jan 21 '19 at 17:34
  • 4
    That page also says, "Although this non-constant space technically takes quicksort out of the in-place category, quicksort and other algorithms needing only O(log n) additional pointers are usually considered in-place algorithms". Heapsort also requires O(log n) space for heapify. – Lee Jan 21 '19 at 17:39
  • Where an in-place sort is required, heap sort will generally do, even if you use a recursive heapify. For practical purposes, then, it is in-place. Trying to establish a more formal and precise definition of "in-place" doesn't appear to be useful. – Matt Timmermans Jan 21 '19 at 18:01

0 Answers0