- Sifting down
- Compared
- Swapped
- In place
Heap sort
Heap sort reads the list as a binary tree and rearranges it into a max-heap, where every parent is at least as large as its children. The largest value is then at the top. Swap it to the end, where it stays, repair the heap, and repeat. The app draws the heap as a tree above the bars, so you can follow each value as it sifts down. Press Play to watch the sort, or Step and Back to go one comparison at a time. Drag the step slider to jump anywhere. The tree above the bars shows the same values as a heap. The tiles count comparisons, swaps and the values taken off the heap. Choose how many bars, how they start, or type your own numbers. With the board selected, the arrow keys step, the space bar plays and pauses, and Home and End jump to the start and the end.
How it works
- Choose how many bars and how they start: random, nearly sorted, reversed, or with few unique values. Or type your own numbers.
- Press Play, or use Step and Back to move one comparison at a time. Drag the step slider to jump anywhere in the sort.
- Watch the tree: first every parent sifts down until the heap is built, then the root is swapped to the end and the heap shrinks by one.
How heap sort works
Read the list as a tree: the value at place i has its children at places 2i + 1 and 2i + 2. Build a max-heap by sifting every parent down, starting with the last parent: while a value is smaller than its larger child, the two swap. When the root holds the largest value, swap it with the last value of the heap. That value is now final, the heap is one shorter, and the new root sifts down to make it a heap again. Repeat until the heap is empty.
Always n log n, in place
The tree has about log₂ n levels, so each sift-down takes at most about 2 log₂ n comparisons, and building the heap takes less than 2n. That gives heap sort a worst case of about 2n log₂ n comparisons, with no buffer: for 40 values, at most 352. Unlike quicksort it has no bad inputs, and unlike merge sort it needs no extra memory. In practice it is usually slower than both, because it jumps around the list, and it is not stable.
Frequently asked questions
How does heap sort work?
It turns the list into a max-heap, a tree stored in the list where every parent is at least as large as its children. Then it repeatedly swaps the largest value, at the root, to the end of the heap and sifts the new root down to repair the heap.
What is a heap?
A complete binary tree stored in a list without pointers: the children of place i are places 2i + 1 and 2i + 2. In a max-heap every parent is at least as large as its children, so the largest value is always at the root, place 0.
Why is building the heap fast?
Most values are near the bottom of the tree and can only sift down a level or two. Adding up the work over all levels gives fewer than 2n comparisons for the whole build, not n log n.
Is heap sort stable?
No. Swapping the root to the end moves values over long distances, so equal values can change order.
Are my numbers sent anywhere?
No. The sort runs in your browser, and your last settings stay in this browser's local storage.
Ready to try it?
Open PictorX in your browser — no install, no credit card required to start.
Go to Editor