Interactive demo
Heapsort Visualization
Heapsort first arranges an array as a binary max-heap and then keeps moving the largest element to the end. It always needs O(n log n) steps and sorts without extra memory.
Press “Next Step” to advance one step at a time, or “Play” to run the algorithm on its own.
Playback
Legend
- Heap element
- Element sifting down
- Compared child
- Larger child
- Final position
Runtime and properties
Best case
O(n log n)
Even a presorted array has to be built into a heap and taken apart again.
Average case
O(n log n)
In each of the n extractions the new root sinks through about log n levels.
Worst case
O(n log n)
The heap only has log n levels, so no input can make sifting down take longer.
Extra memory
O(1)
The heap lives inside the array, only a few variables are needed.
Stable
No
Moving the root to the end jumps over equal elements.
In-place
Yes
The heap is built and taken apart within the array.
n is the number of elements. O(n log n) is the best a sorting algorithm based on comparisons can achieve.
Compared with the other sorting algorithms
| Algorithm | Best case | Average case | Worst case | Extra memory | Stable | In-place |
|---|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Yes |
| Heapsort this page | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
1. The heap is the array
The array is read as a binary tree: the children of the element at index i sit at 2i + 1 and 2i + 2. The tree above the bars shows exactly the same elements.
2. Build a max-heap
Starting at the last parent, each element sinks down by swapping with its larger child until it is not smaller than its children. Afterwards the root holds the maximum.
3. Sort
The root is swapped with the last heap element, which puts the maximum in its final position. The heap shrinks by one and the new root sinks down to repair it, until the heap is empty.