Sorting Algorithms

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
Speed

Step 1 of 87

Heap sort, 12 values in random order.

Counters

Comparisons
0
Writes
0
n
12
Average case
O(n log n)

Settings

Starting order

Two to 48 numbers. Sorted in exactly the order you type them.

Heap sort

  1. 1for i in n/2-1 .. 0:
  2. 2 siftDown(i, n) // build max-heap
  3. 3
  4. 4for end in n-1 .. 1:
  5. 5 swap(0, end) // root is the max
  6. 6 siftDown(0, end)
  7. 7
  8. 8siftDown: sink a value past its
  9. 9larger 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.

  1. Merge3344 writes
  2. Quick3340 writes
  3. Insertion4042 writes
  4. Shell4637 writes
  5. Heap5166 writes
  6. Bubble6062 writes
  7. Selection6618 writes

How the seven compare

AlgorithmBestAverageWorstExtra memoryStable
BubbleO(n)O(n²)O(n²)O(1)Yes
InsertionO(n)O(n²)O(n²)O(1)Yes
SelectionO(n²)O(n²)O(n²)O(1)No
ShellO(n log n)O(n√n)O(n²)O(1)No
MergeO(n log n)O(n log n)O(n log n)O(n)Yes
QuickO(n log n)O(n log n)O(n²)O(log n)No
HeapO(n log n)O(n log n)O(n log n)O(1)No

Stable means equal values keep their original order.

Complexity

BestAverageWorstExtra memory
O(n log n)O(n log n)O(n log n)O(1)

The only comparison sort with an n log n guarantee and constant extra space. It loses to quicksort in practice because its accesses jump around the array and defeat the cache.

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.

  1. Build the heap: sift down from the last parent back to the root. Bottom-up building is O(n), not O(n log n).
  2. Swap the root — the largest remaining value — with the last element of the heap region.
  3. Shrink the heap region by one. The value just parked is in its final position.
  4. Sift the new root down: repeatedly swap it with its larger child until it is at least as large as both.
  5. Repeat until the heap holds one element.

Implementation

The same algorithm the visualiser is running, written to be read.

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 values

When 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.

Check yourself

If the animation made sense, these should too.

Why is building the heap O(n) rather than O(n log n)?

Because sifting down from the bottom up does work proportional to each node's height, and most nodes are near the bottom where the height is small. Half the nodes are leaves and cost nothing; the sum over all heights converges to about n, not n log n.

Heapsort has heapsort's guarantee and no extra memory. Why is quicksort still the usual default?

Memory access. Sifting a value down jumps from index i to 2i+1, so consecutive comparisons touch distant cache lines, while quicksort's partition scans linearly. The asymptotics are better; the constant factor is not.

More sorting algorithms