Heap sort, explained

Heap sort uses a heap, a tree stored inside the list where every parent is bigger than its children (a max-heap). That means the largest value is always at the top.

The algorithm builds the heap, then repeatedly swaps the top value to the end of the list and repairs the heap.

How it works

• Rearrange the list into a max-heap so the largest value is first.
• Swap the first item with the last unsorted item. The largest value is now in its final place.
• Shrink the heap by one and repair it so the largest remaining value is at the top.
• Repeat until the heap is empty.

A small example

Sort this list:

4 10 3 5 1

Build max-heap:           10 5 3 4 1
10 moves to the end:      (heap) 5 4 3 1 | 10
5 moves to the end:       (heap) 4 1 3 | 5 10
4 moves to the end:       (heap) 3 1 | 4 5 10
3, then 1 follow:         1 3 4 5 10

What to know about its cost

• O(n log n) in the best, average and worst case.
• Uses O(1) extra space, because it sorts in place.
• Not stable.

Where it works well

• Predictable speed with no bad case.
• No extra memory needed.

Where it struggles

• Usually slower than quick sort in practice.
• Not stable, and jumps around in memory.

Try it yourself

Open the Sorting experiment, enter the list 4 10 3 5 1, choose Heap Sort and step through it. Then use the comparison view to run another algorithm on the same list and compare the comparisons and swaps.

Open the Sorting experiment