How Heapsort Works
Heapsort turns the array into a max-heap in place, then repeatedly swaps the root to the end and sifts the new root down. O(n log n) guaranteed, in O(1) extra space.
- Waiting
- Being compared
- Just moved
- In final position
Heap sort, 12 values in random order.
Counters
- Comparisons
- 0
- Writes
- 0
- n
- 12
- Average case
- O(n log n)
Settings
More options
Two to 48 numbers. Sorted in exactly the order you type them.
Heap sort
- 1
for i in n/2-1 .. 0: - 2
siftDown(i, n) // build max-heap - 3
- 4
for end in n-1 .. 1: - 5
swap(0, end) // root is the max - 6
siftDown(0, end) - 7
- 8
siftDown: sink a value past its - 9
larger child until the heap holds
The same array, every algorithm
Comparisons on the values above, cheapest first. Writes in the second line. Run it on nearly sorted values to see the O(n log n) sorts lose.
- Merge3344 writes
- Quick3340 writes
- Insertion4042 writes
- Shell4637 writes
- Heap5166 writes
- Bubble6062 writes
- Selection6618 writes
How the seven compare
| Algorithm | Best | Average | Worst | Extra memory | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Shell | O(n log n) | O(n√n) | O(n²) | O(1) | No |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
Scroll the table sideways for the rest of the columns.
Stable means equal values keep their original order.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(n log n) | O(n log n) | O(n log n) | O(1) |
How heapsort works
Heapsort reads the array as a binary heap: the children of index i live at 2i+1 and 2i+2. It first rearranges the array so every parent is at least as large as its children, which puts the maximum at index 0. Then it swaps index 0 with the last unsorted position, parking the maximum where it belongs, shrinks the heap by one, and sifts the new root down to restore the heap property.
- Build the heap: sift down from the last parent back to the root. Bottom-up building is O(n), not O(n log n).
- Swap the root, which is the largest remaining value, with the last element of the heap region.
- Shrink the heap region by one. The value just parked is in its final position.
- Sift the new root down: repeatedly swap it with its larger child until it is at least as large as both.
- Repeat until the heap holds one element.
Implementation
def heap_sort(values):
n = len(values)
def sift_down(root, end):
while True:
largest, left, right = root, 2 * root + 1, 2 * root + 2
if left < end and values[left] > values[largest]:
largest = left
if right < end and values[right] > values[largest]:
largest = right
if largest == root:
return
values[root], values[largest] = values[largest], values[root]
root = largest
# Bottom-up build is O(n), not O(n log n).
for parent in range(n // 2 - 1, -1, -1):
sift_down(parent, n)
for end in range(n - 1, 0, -1):
values[0], values[end] = values[end], values[0]
sift_down(0, end)
return valuesWhen to use it
- Use it when a worst case matters and memory does not stretch: real-time systems and anything that must not degrade on adversarial input.
- Use its machinery for a priority queue, which is the same structure without the final sort.
- Avoid it when raw speed on random arrays is the goal. Its memory access pattern is cache-hostile, and quicksort wins on the same data.