NOTE

Heap Sort

In-place comparison sorting using heap construction followed by repeated root extraction.

Data Structures & AlgorithmsCreated 02/29/2020Updated 09/15/20261 min readhistorical

This is a historical learning note and may contain outdated or incomplete understanding.

Heap sort builds a max-heap (for ascending output), then repeatedly swaps the root with the end of the unsorted region and restores the heap.

Bottom-up heap construction is O(n); the full sort is O(n log n) worst-case and can operate in-place with O(1) auxiliary array storage.

Heap sort is generally not stable and often has poorer locality/constants than tuned quicksort variants.