Heapsort

O(n log n) guaranteed (like merge) AND in place (like quicksort). Built on the binary heap.

The array is the tree

• Node i's children live at 2i+1 and 2i+2 — no pointers
• Max-heap: every parent ≥ its children → max at index 0
• Build the heap, then extract the max n−1 times
• Each extraction: swap root to the end, sift the new root down

Watch the sorted tail grow

Orange max → swaps to the right (green sorted), new max sifts up. In place, no second array.

No bad case

Random, sorted, reversed — all the same time. (Quicksort blew up 141×.)

Best Big-O, not fastest

• O(n log n) worst case + O(1) space — the only sort with both
• But cache-hostile (i → 2i+1 → 4i+3 …) → slower than quicksort
• Building the heap is O(n), not O(n log n)
• The guarantee behind introsort's fallback

Takeaway

Heapsort trades everyday speed for an unconditional guarantee. Big-O and reality part ways. Next: beat O(n log n) by not comparing.