Smoothsort Demystified (2011)

Finally, given a binary heap, one can remove the maximum element from the heap and rearrange the nodes to restore the heap property in O(lg n) time. Since we can build the max-heap in O(n) time and rebalance the heap in O(lg n) time, the overall runtime is O(n + n lg n) = O(n lg n), which is asymptotically optimal. Because the heap is represented implicitly using the array itself, only a constant amount of memory must be used beyond the array itself to store the state of the algorithm (in particular, things like the next position to consider, data for the rebalance heap step, etc.) Consequently, this version of heapsort runs in O(n lg n) time and O(1) auxiliary space.

Source: www.keithschwarz.com