Heapsort

Heapsort is a comparison-based sorting algorithm with guaranteed O(n log n) worst-case time complexity, invented by J. W. J. Williams in 1964. It operates by first building a binary heap — a complete binary tree satisfying the heap property — and then repeatedly extracting the maximum (or minimum) element, placing it at the end of the array and restoring the heap invariant. Unlike Quicksort, its performance does not depend on input distribution or pivot selection, which makes it the algorithm of choice when worst-case guarantees matter more than average-case speed.

Heapsort's in-place implementation and deterministic bounds make it the robust counterpart to quicksort's efficient fragility. Introsort exploits this complementarity by delegating to heapsort when quicksort's recursion depth indicates unbalanced partitioning. Yet heapsort's poor cache locality — the sift-down operation jumps through memory in a tree-like pattern rather than scanning contiguous regions — means it is often slower than quicksort in practice even when the latter operates in worst-case quadratic time. The algorithm is a textbook illustration of the efficiency-robustness tradeoff: guaranteed performance is not free, and the cost is paid in memory hierarchy efficiency.