Heapsort

Heapsort is a sorting algorithm that builds a max-heap inside the array and then swaps the root, the largest item left, to the back of the heap, one extraction at a time, until the array is sorted. It guarantees O(n log n) on every input with O(1) extra memory, which no other sort in this section does, and it pays with instability and a slower average than quicksort. The topic opens on the extraction phase, with the boundary between the heap and the sorted items moving one step per extraction, then walks through the bottom-up build that comes first. A gotcha shows what a sift-down does when it is allowed past that boundary, and the code card shares one sift-down between both phases in three languages. A concept card shows heapsort reordering equal keys and counts its comparisons against quicksort's, and an exercise sorts five tournament scores in place.