Analyzing Heapsort

In-place heapsort sorts an array of $n$ values in two phases.

buildHeap reads the array as a complete tree in level order and sinks each internal node once, from the last one back to the root.
sortdown runs $n - 1$ turns. Each turn swaps the root with the last slot of the heap, shrinks the heap by one, and sinks the new root.

A sink moves a value down one level per step.

Solution

The build is $O (n)$ . A node can sink at most as many levels as there are beneath it. About half the nodes are leaves and do not sink at all, about a quarter sink at most one level, and only the few nodes near the top can sink far. Added up, the total number of sink steps is $O (n)$ .

Solution

Every sortdown sink starts at the root, and the root has the whole remaining heap beneath it. So each of those sinks can take up to about $lo g n$ steps, and the sortdown is $O (n lo g n)$ .

Solution

The running time is $O (n lo g n)$ : an $O (n)$ build followed by an $O (n lo g n)$ sortdown.
The auxiliary space is $O (1)$ . Both phases only swap values within the input array, using a few index variables and one temporary in swap.