A heapsort loop swaps the root to the last unsorted slot, then sifts down over the whole array — what breaks?

## The invariant this bug violates Heapsort's extract phase is governed by a single invariant, and every line of the loop exists to preserve it. At the top of each iteration: ``` [ 0 .............. end ][ end+1 ......... n-1 ] a max-heap sorted output, all >= everything in the heap region ``` Two clauses matter. First, the prefix satisfies the heap property. Second — and this is the clause the bug destroys — the suffix is **frozen**: those slots hold their final values and no operation may read or write them again. ## What the buggy call actually does Suppose the array is a valid max-heap of size `n`, so `a[0]` is the global maximum. The loop swaps `a[0]` with `a[end]` where `end = n-1`. Now the global maximum is at `a[n-1]` — correct and final — and some small element is sitting at the root, violating the heap property inside the prefix. Sift-down is supposed to repair the prefix. Call it with size `n` instead of `end`, and sift-down treats index `n-1` as an ordinary heap node. Walking down from the root it eventually reaches that slot's subtree, sees the largest value in the whole array, and swaps it upward. Within a few iterations the maximum is back at or near the root, gets swapped to the tail again, and the loop churns. Concretely with `[9, 7, 5, 3]`: swap gives `[3, 7, 5, 9]`; a full-length sift-down from the root compares 3 against children 7 and 5, swaps with 7, then compares 7 against child 9 and swaps — leaving `[7, 9, 5, 3]`, with the finished 9 dragged back inside and the 3 now buried. The loop still terminates after n-1 rounds, but the output is unsorted. ## Why reviewers miss it Three things make this a genuinely hard review catch: 1. **It compiles and terminates.** The loop counter is independent of the bug, so there is no hang and no out-of-bounds access — every index touched is legal. 2. **Small inputs can accidentally pass.** With one or two elements, or with input where the tail happens not to outrank the heap, the output can look right. A test suite that sorts three-element arrays may go green. 3. **The two sizes are both "obviously" correct-looking.** `n` is the array length, and every other part of the algorithm does think in terms of the whole array. Only the extract loop needs the shrunken view. The defensive habits that catch it: assert the invariant in a debug build ("the sorted suffix is non-decreasing and its minimum is >= the heap's maximum"), give sift-down an explicit `size` parameter rather than letting it read a length from anywhere ambient, and property-test against a reference ordering with randomized inputs of a few hundred elements rather than hand-written tiny cases. ## The sibling mistakes in the same loop While you are reviewing this loop, three neighbouring off-by-ones live in the same three lines: - **Shrinking after the sift instead of before.** If `end` is decremented after sift-down runs with the old size, the freshly placed maximum is still visible to the sift — the same corruption, one round later. - **Looping while `end >= 0` instead of `end > 0`.** Harmless but pointless: a heap of one element is already a heap, and sifting down from a root with no children does nothing. - **Sifting from the wrong index.** Sift-down must start at the root, index 0, because that is the only position the swap could have violated. Starting anywhere else leaves the heap broken. ## The general lesson Any algorithm that partitions one buffer into a live region and a finished region has this failure mode: every operation on the live region must be handed the boundary explicitly, and the finished region must be unreachable by construction. When you can, make the boundary a parameter rather than a shared variable — a function that cannot see the whole array cannot corrupt the part it should not touch.