The Heapsort Algorithm

Merge sort guarantees O(n log n) by using an extra array. Heapsort gets the same guarantee in place, with no second array at all, by borrowing a data structure usually associated with priority queues: the binary heap.

The idea

A binary heap stored in a plain array uses arithmetic instead of pointers: for any index i, its children live at 2i + 1 and 2i + 2. A max-heap keeps one invariant everywhere in that implicit tree: every parent is greater than or equal to both of its children — which forces the single largest value to sit at the root, index 0, though says nothing about the order of anything else.

Heapsort works in two phases. First, build a max-heap out of the entire array — turning an arbitrary arrangement into one that satisfies the heap invariant everywhere, without fully sorting anything yet. Then, repeatedly extract the maximum: the root is always the largest value left, so swap it to the end of the still-unsorted region, shrink the heap by one, and restore the heap invariant at the root. Doing that once per remaining element sorts the whole array, largest-to-last, one extraction at a time.

Both phases rely on the same operation: sift down. Given a node that might violate the heap invariant against its children, compare it with both, swap with whichever child is larger if either one is, and repeat at the new position — down the tree, never back up — until the node is either a leaf or bigger than both its children.

Implementation

#include "plot.hpp"
#include <stdlib.h>

const int N = 20;
int values[N];
bool settled[N];

int heapSize = N;
int buildIndex = N / 2 - 1;
bool building = true;
int extractEnd = N - 1;
int cur = -1;   // node currently being sifted down; -1 = need the next task
bool done = false;
int tick = 0;

void setup() {
    PlotCanvas(640, 480);

    for (int n = 0; n < N; n++) {
        values[n] = n + 1;
        settled[n] = false;
    }

    srand(1);
    for (int n = N - 1; n > 0; n--) {
        int r = rand() % (n + 1);
        int tmp = values[n];
        values[n] = values[r];
        values[r] = tmp;
    }
}

void frame() {
    // Slow the animation down: one step every few calls to frame() instead
    // of one per call, so individual comparisons stay visible.
    if (!done && ++tick >= 4) {
        tick = 0;

        if (cur == -1) {
            if (building) {
                if (buildIndex >= 0) {
                    cur = buildIndex;
                    buildIndex--;
                } else {
                    building = false; // heap property established, extract next
                }
            } else if (extractEnd <= 0) {
                done = true;
            } else {
                int tmp = values[0];
                values[0] = values[extractEnd];
                values[extractEnd] = tmp;
                settled[extractEnd] = true; // max of the remaining heap, now final
                heapSize = extractEnd;
                extractEnd--;
                cur = 0;
            }
        } else {
            int left = 2 * cur + 1;
            int right = 2 * cur + 2;
            int largest = cur;
            if (left < heapSize && values[left] > values[largest]) largest = left;
            if (right < heapSize && values[right] > values[largest]) largest = right;

            if (largest != cur) {
                int tmp = values[cur];
                values[cur] = values[largest];
                values[largest] = tmp;
                cur = largest;
            } else {
                cur = -1; // sifted as far down as it needs to go
            }
        }
    }

    PlotBackground(250, 250, 250);

    int barWidth = plot_width / N;
    for (int idx = 0; idx < N; idx++) {
        if (done) {
            PlotColor(70, 170, 90);   // fully sorted
        } else if (idx == cur) {
            PlotColor(220, 60, 60);   // being sifted down right now
        } else if (settled[idx]) {
            PlotColor(70, 170, 90);   // extracted into final position
        } else {
            PlotColor(30, 100, 200);  // part of the heap, not yet extracted
        }

        int height = values[idx] * (plot_height - 20) / N;
        int x0 = idx * barWidth + 1;
        int x1 = x0 + barWidth - 2;
        int y0 = plot_height - height;
        int y1 = plot_height;
        PlotFilledRectangle(x0, y0, x1, y1);
    }
}

cur holds the node currently sifting down, or -1 when nothing is sifting and the next task needs to be picked: during the build phase that means starting a sift at the next buildIndex (counting down from the middle of the array — leaves need no sifting, since they have no children); during the extract phase it means swapping the root with values[extractEnd], marking that position final, shrinking heapSize, and starting a sift at the root. One call to frame() performs one comparison-and-possibly-swap step of whichever sift is active.

• blue — part of the heap, not yet extracted
• red — the node currently being sifted down
• green — extracted into its final sorted position

Walking through an example

Sifting down [1, 8, 4] (index 0 holds 1, its children hold 8 and 4) to restore the heap invariant at the root:

After swapping, the array is [8, 1, 4] and the max-heap invariant holds: 8 ≥ 1 and 8 ≥ 4. Index 1 has no children here, so the sift stops. Building a full heap repeats this for every non-leaf node, starting from the lowest ones so that by the time a sift reaches a higher node, everything below it is already a valid (smaller) heap.

Why the in-place guarantee matters

Heapsort matches merge sort's worst-case O(n log n) bound — both do log n levels of work, O(n) per level, unconditionally — but does it using O(1) extra memory instead of a second array the size of the input. That makes it attractive exactly where merge sort's extra allocation is a problem: memory-constrained systems, or anywhere an in-place worst-case guarantee is needed without quicksort's input-dependent risk.

The trade-off is cache behavior: heapsort's 2i + 1 / 2i + 2 accesses jump around the array rather than sweeping through it sequentially, the way merge sort's linear merges and quicksort's linear partitioning scans do. In practice this tends to make heapsort slower than quicksort or merge sort on typical inputs, despite matching or beating both on asymptotic guarantees — which is exactly why introsort uses quicksort by default and only falls back to heapsort as a bound on the worst case, rather than using it directly.

Conclusion

Heapsort reframes sorting as a sequence of priority-queue operations: build a structure that always exposes its maximum at the root, then remove that maximum, one element at a time, cheaply enough that n extractions from a shrinking heap still add up to only O(n log n). It is a good reminder that "sort a list" and "repeatedly find the biggest remaining item" are the same problem looked at from two directions.