HEAP SORT uses MAX_HEAPIFY function which calls itself but it can be made using a simple while loop and thus making it an iterative function which inturn takes no space and hence Space Complexity of HEAP SORT can be reduced to O(1).
while ( i < = heapsize) { lc <- left(i) rc <- right(i) if (lc<=heapsize) and (A[lc]>A[i]) largest <- lc else largest <- i if (rc<=heapsize) and (A[rc]>A[largest]) largest <- rc if (largest != i) { exchange A[i] <-> A[largest] i <- largest } else break }
http://stackoverflow.com/questions/22233532/why-does-heap-sort-have-a-space-complexity-of-o1
64.3k questions
77.9k answers
244k comments
80.0k users