Heapsort

By Victor Arce

Heapsort sorts by turning the array into a binary heap — a complete binary tree where every parent is at least as large as its children — and then pulling the maximum out of the top, over and over. The clever part is that the tree lives inside the array itself: the children of position i are at 2i+1 and 2i+2, so no extra structure is needed.

Step through it below. The same values are shown as the array (above) and as a binary tree (below); the → marks the node being sifted (its children are boxed in the array), and the green tail is the sorted region. Toggle show log to follow along in words.

How it works

There are two phases:

1. Build a max-heap. Starting from the last parent and working back to the root, sift each node down: compare it with its larger child and swap if the child is bigger, repeating until the node sits above both children. After this pass the largest value is guaranteed to be at the root.
2. Sort by extraction. Swap the root (the maximum) with the last heap element, shrink the heap by one so that value is now in its final sorted place, and sift the new root down to restore the heap. Repeat until the heap is empty — the array is sorted, growing from the back.

Cost

Building the heap is O(n)O(n) — linear time: the work grows in direct proportion to the number of items n., and each of the n extractions costs O(log n) to sift down, so heapsort runs in O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts. in the best, average, and worst case — its time never degrades on bad inputs the way quicksort's can. It sorts in-placeIn-place: sorts within the original array using only a little extra memory (no second array). (only a constant amount of extra memory), which is its big advantage over merge sort. The trade-off: it is not stableStable: equal values keep their original relative order after sorting., and its scattered, cache-unfriendly memory access usually makes it a little slower in practice than a well-tuned quicksort, so it's often used as a safe fallback (e.g. in introsort).

Back to Sorting Algorithms