Heapsort
Read the array as a tree, where index k has children 2k + 1 and 2k + 2. Rearrange it so every parent beats its children, and the largest value sits at the root. Swap it to the end, repair the heap, repeat.
53819274
The array is already a tree: index k has children 2k + 1 and 2k + 2. Press play to turn it into a heap.
1function heapsort(a) {2 const n = a.length;3 for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {4 siftDown(a, i, n);5 }6 for (let end = n - 1; end > 0; end--) {7 swap(a, 0, end);8 siftDown(a, 0, end);9 }10}1112function siftDown(a, i, size) {13 while (2 * i + 1 < size) {14 let child = 2 * i + 1;15 if (child + 1 < size && a[child] < a[child + 1]) child++;16 if (!(a[i] < a[child])) return;17 swap(a, i, child);18 i = child;19 }20}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n log n | every input: each pull sifts down the full height |
| average | n log n | random input |
| worst | n log n | no bad input exists |
| space | 1 | the heap lives inside the array itself |
Where it breaks
- Slower than quicksort in practice. Sifting jumps from i to 2i + 1, all over memory, so it makes poor use of the CPU cache. It wins on guarantees, not speed. Introsort uses it as a fallback when quicksort starts going quadratic.
- Sorted input does not help. Pick Sorted above: building the heap moves the largest values to the front first, so it does about as much work as random input.
- Equal keys can swap order. Pulling the root to the end jumps it past everything in between. So it is not stable.