Heapsort

In a max-heap, parents are no smaller than children, so the root is maximal. A complete binary-tree layout can be represented by array indexes. Heap order does not fully sort siblings or whole subtrees.

Heapsort maintains this structure inside the input array. Like repeatedly removing values from a priority queue, it selects an extremum, but it need not build a separate output container: one region remains a heap while another holds final maxima.

References: [1]

Bottom-up construction visits internal nodes from the last parent back toward the root, sinking each after its child subtrees are heaps. Some sinks have logarithmic length, but most nodes are near the bottom, allowing O(n) total construction.

During sortdown, the root exchanges with the heap’s last item. The heap shrinks and the replacement root sinks. Each removed maximum is in its final position outside further repairs, producing ascending order after the heap is exhausted.

References: [1]

Each extraction repairs at most one height-length path, giving O(n log n) total worst-case time without a random-input or balanced-pivot assumption. Under constant-cost comparisons, an iterative array implementation also uses O(1) extra storage.

Ordinary heapsort is unstable because distant exchanges can change equal-key order. A constructed heap is not a fully sorted array, so its arbitrary positions do not provide sorted ranks. Comparison costs and actual memory behavior still matter when choosing between algorithms with similar asymptotic bounds.

References: [2] [1]