Build a max-heap in the array itself, then repeatedly swap the root to the end, shrink the heap by one and sift the new root down. The array is a heap and a sorted suffix at the same time, so no extra memory is needed at all, and the comparison count is Θ(n log n) on every input. What it gives up is stability and adaptivity, neither of which any complexity class was ever going to supply.
Core ideas
The heap itself was “Priority Queues and Binary Heaps”. What is new is the trick that makes the sort need no second array.
Slots 1 … m are the heap and slots m+1 … n are the finished suffix, in increasing order. Each round swaps the largest remaining key, which is at the root, into slot m, then decrements m and sifts the displaced key down through the smaller heap. Nothing is allocated, and the boundary between “heap” and “sorted” is a single index.
A sift-down through a heap of m elements costs at most 2⌊log₂ m⌋ comparisons, so the teardown is Θ(n log n) whatever the input was, and the build is Θ(n) by the argument of “Building a Heap in Linear Time”. No input is bad. Equally, no input is good: at 16 keys the lab measures 85 comparisons on already-increasing input, 80 on a shuffle and 72 on decreasing input. Already-sorted input was the dearest of the three.
The build alone moves keys across the whole array: slot n can end up at the root. So two equal keys can be swapped past each other before the sort proper begins, and the lab shows it on eight records with four distinct keys, where three pairs come out reversed. Merge sort shares heapsort's complexity class and is stable; the class was never the reason.
The material
The two phases and their counts, what the in-place trick costs, and the counterexample to stability.
Heapsort sorts a[1..n] in two phases. Build: rearrange a into a max-heap in place, bottom up. Teardown: for m = n down to 2, swap a[1] with a[m], treat the heap as having m − 1 elements, and sift the new a[1] down until the heap property holds again.
The max-heap is the choice that makes the sort ascending. The root is the largest remaining key, and the slot it is swapped into is the last slot the heap still owns, so the largest key lands where the sorted array wants it and is immediately outside the heap.
On 8 1 3 6 5 2 7 4 the build costs 8 comparisons and produces the heap 8 6 7 4 5 2 3 1. The seven rounds of teardown cost 18 more, so heapsort spends 26 comparisons in all and performs 20 swaps. Merge sort on the same eight keys spends 17, and ⌈log₂ 8!⌉ = 16 comparisons are necessary for any comparison sort on any array of eight. Every one of those three numbers was produced by running something.
The build is the cheap half and it is the half readers expect to dominate. At 16 keys the lab measures 22 comparisons for the build and 58 for the teardown, out of 80. The asymmetry is structural: the build's cost is dominated by the many nodes near the bottom, which sift down almost no distance, while every round of the teardown drops a key from the root and usually carries it most of the way back down.
It is not adaptive. The comparison counts at 16 keys are 85 for increasing input, 80 for a shuffle, 72 for decreasing input: not only is sorted input no cheaper, it is the most expensive of the three, because an ascending array is the worst possible starting shape for a max-heap build and every key has to travel. A reader who expects “nearly sorted input is cheaper” is expecting a property insertion sort has and this algorithm does not.
It is not stable. The lab's tie test builds eight records with four distinct keys, 1#1 2#2 3#3 4#4 1#5 2#6 3#7 4#8, and heapsort returns 1#5 1#1 2#6 2#2 3#3 3#7 4#8 4#4. Three pairs of equal keys come out reversed. One would have been enough.
What it does promise is worth being clear about, because it is the reason the algorithm is used. Θ(1) extra memory, and a Θ(n log n) worst case with no bad input and no randomness — which is exactly what quicksort cannot offer and merge sort can only offer at the cost of a second array. When memory is the binding constraint and a guarantee is wanted, this is the sort.
The cost of those two promises is a constant factor, and the lab prints it as a ratio. At 16 keys heapsort spends 80 comparisons against merge sort's 48 on the same array: both are Θ(n log n) and heapsort's constant is larger, chiefly because a sift-down compares the key with both children at every level. That same factor of about two reappears in “k-Way Merging and Sorting in Practice”, where a heap merges k runs and pays for it in exactly the same way.
Two figures on this page are measurements of one array each — 26 at eight keys, 80 at sixteen — and one is a proof: ⌈log₂ n!⌉, which no comparison sort can go under on any array. At 16 keys that is 45, and merge sort's 48 and heapsort's 80 both sit above it. The gap between 45 and 80 is not slack in the bound; it is the price of the two promises.
Interactive
Build, then swap the root to the end and sift down
Method
Draw the array once and keep two marks on it: where the heap ends, and where the sorted suffix begins.
Start at the last internal node, ⌊n/2⌋, and work back to the root, sifting each down. Count one comparison per pair of children examined plus one against the parent. On eight keys this is 8 comparisons; check yours against the lab's build column.
Exchange a[1] with the last slot the heap owns. Write the boundary down. That key is final and will not be looked at again — which is the whole reason no second array is needed.
At each level compare the two children with each other, then the larger with the parent. Stop when the parent wins or the node has no children. The number of levels it travels is what varies between rounds; the maximum is ⌊log₂ m⌋.
Put heapsort's count beside merge sort's on the same array and beside ⌈log₂ n!⌉. Both sorts are above the bound and heapsort is above merge sort; the question that has an answer here is how big the constant is, not which sort is faster.
Run increasing, decreasing and shuffled at the same length. If sorted input came out cheapest you would have found an adaptive algorithm; it comes out dearest, and that is the promise heapsort does not make.
Move the keys slider to 8 and leave the arrival order on the fixed shuffle. The array is 8 1 3 6 5 2 7 4. The build is written out as four sift-downs; the teardown is written as the array after each round, which is what the lab's upper stage draws.
Two things in that trace are worth pausing on. The build made 8 comparisons and the teardown 18, so the phase that sounds expensive is the cheap one. And the sorted suffix grows from the right while the heap shrinks from the same boundary, which is why the extra memory is a single index.
The comparison totals are not a verdict about speed. Merge sort made fewer comparisons on this array and needs Θ(n) more memory to do it; the bound of 16 says neither of them is doing anything impossible. What heapsort bought with its 26 is a guarantee that holds on every array of eight keys and a memory footprint of zero.
For a faded rehearsal, set the arrival order to already increasing at the same length. The supplied first move is a prediction: the build has more work to do, not less, because an ascending array is the worst possible shape for a max-heap. Count the build's comparisons by hand before you read them off, then compare the total with the 26 above.
You should be able to build a max-heap bottom up by hand, carry out the teardown with the boundary marked, count build and teardown separately, and say which two of the four promises heapsort breaks and why no complexity class was going to decide either.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.