Heapsort

## The heap is the array The thing that surprises people first about heapsort is that no heap is ever *built* as a separate data structure. A complete binary tree can be laid out level by level in a flat array, and then the parent/child links are arithmetic rather than pointers: - children of index `i` are `2i + 1` and `2i + 2` (0-based) - parent of index `i` is `(i - 1) / 2`, integer division - an array of length `size` has internal nodes at indices `0 .. size/2 - 1`; everything past that is a leaf Because the tree is *complete* (every level full except possibly the last, which fills left to right), there are no gaps, so the array wastes nothing on structure. This implicit representation is the entire reason heapsort can sort with O(1) auxiliary space while a merge-based sort in its standard array form needs an O(n) scratch buffer. ## Two phases, one array **Phase 1 — build.** Rearrange the input into a max-heap: every node is greater than or equal to its children, so the global maximum sits at index 0. Done bottom-up, this phase costs O(n), not O(n log n) — the linear bound has its own derivation and is a heap-mechanics topic in its own right. **Phase 2 — extract.** Maintain a boundary `end` that marks the last slot still belonging to the heap. Repeat until one element is left: 1. `swap(a[0], a[end])` — the maximum of the remaining heap moves to the slot it will occupy forever. 2. `end = end - 1` — the heap shrinks by one; the sorted region grows by one. 3. Sift the new root down **over the shrunken heap only**, restoring the heap property in O(log size). At the top of every iteration the array is two disjoint regions with a hard invariant: ``` [ 0 .............. end ][ end+1 ......... n-1 ] max-heap, unsorted sorted, final, and every element here is >= every element there ``` When the heap region shrinks to a single element, that element is the smallest, and it is already at index 0 — where it belongs. So the loop stops at `end == 0`; there is nothing left to place. ## Why the output comes out ascending from a max-heap This trips people up: a max-heap gives you the *largest* element first, yet the result is ascending. That is exactly because the largest element is written to the *back* of the array and the region behind the boundary is filled right to left. If you want descending order in place, you build a min-heap instead and the same machinery fills the tail with the smallest elements. There is no reversal step in either direction. ## The cost sheet - Build: O(n). - Extract loop: n-1 sift-downs, each O(log n) → O(n log n). - Total: O(n log n) **worst case**, and also O(n log n) best case — heapsort is not adaptive, so already-sorted input buys you essentially nothing. That flatness is a feature when you need a predictable bound and a drawback when your data is usually nearly ordered. - Auxiliary space: O(1) for the standard iterative form. Note the qualifier: if sift-down is written recursively, the call stack is O(log n), and recursion depth is genuinely part of space complexity — it just does not change the practical story here. ## What "in place" actually promises In place means O(1) auxiliary space (or O(log n) for recursion), not "never moves anything" and not "cache-friendly". Heapsort touches the array with long-range swaps, which is precisely why it can be slower in wall-clock terms than a sort with the same asymptotics but sequential access. In place is a *memory* guarantee, not a *speed* guarantee — a distinction interviewers like to poke at. One more consequence worth internalising: because the algorithm allocates nothing at all, it cannot fail partway through for lack of memory. On systems where an allocation failure mid-sort is unacceptable, that property matters more than a constant factor of speed.