Recap: Heapsort

Build bottom-up, extract to the boundary, O(n log n) in O(1) space, and not stable.

Heapsort sorts an array in place by building a max-heap and moving its largest item to the back, one extraction at a time, which guarantees O(n log n) on every input with O(1) extra memory. This card gathers what the topic established and where each idea was taught.

What the topic established, and which card it was on
The idea	Where
The array holds a max-heap before the boundary and the sorted items after it, and each extraction moves the boundary one step	Heapsort: Build a Max-Heap, Then Move the Largest to the End
Sifting down every parent from index ⌊n/2⌋ − 1 back to the root builds the heap in O(n)	Build the Starting Max-Heap From the Bottom Up
An extraction's sift-down must stop at the boundary, or it pulls sorted items back into the heap	Sifting Down Past the End of the Heap
One sift-down serves both phases, bounded by n in the build and by end in each extraction	Heapsort in Python, Java and TypeScript
The swap to the end jumps over equal keys, and heapsort makes more comparisons than quicksort	Why Heapsort Is Not Stable
Five scores built into 90 84 47 61 73 and reached 73 61 47 84 90 after two extractions	Practice: Ranking Tournament Scores Without a Second Array

Heapsort on n items

Build phase: O(n); every case; most parents sit near the bottom and fall a level or two
Extraction phase: O(n log n); worst and average case; n − 1 sift-downs from the root
Whole sort: O(n log n); worst case, on every input
Extra space: O(1); no second array and no recursion
Stable: No; the root's swap to the end jumps over equal keys

Heapsort is the sort that cannot be made slow and needs no memory beyond the array, and it pays for both with instability and a slower average than quicksort. Choosing a Sorting Algorithm, a later topic, sets it against quicksort, merge sort and the built-in sorts.

← → move through sections and cards