Heap sort: build a heap, then empty it from the back

Quick sort sorts a million random values in about 25 million comparisons, but the wrong order costs it 500 billion. Merge sort never needs more than about 20 million, but it borrows a second array as long as the first. The Linux kernel wants neither: its code runs on a small, fixed stack, where deep recursion and big buffers are unwelcome, and a sort that some input makes crawl is a weakness. So the kernel's array sort is heap sort: O(n log n) on every input, with a few variables as its only extra memory.

The idea comes from the heaps lesson: a max-heap keeps its largest value on top, so taking the top out again and again hands the values back largest first. The trick is where they go: each removal frees the last cell of the heap, and that cell is exactly where the value removed belongs.

max-heap

A complete binary tree in the array, with the children of index i at 2i + 1 and 2i + 2 and no child larger than its parent, so the largest value is at index 0.

build-heap

Sifting down every parent, from the last, at ⌊n/2⌋ − 1, back to the root, which makes the whole array a max-heap in O(n).

sift down

Swapping a value with its larger child while that child is larger, so it sinks until the heap holds again.

heap part and sorted part

Positions 0 to size − 1 form the heap; positions size to n − 1 hold the largest values in their final places.

stable

Equal values keep their starting order, which matters when you sort records by one field.

Here are the quick sort lesson's 8 values. The tree is only in the index arithmetic: i marks the sinking value, c its larger child, and brackets under the bars show the heap part and the sorted part.

The first loop is the bottom-up build from the heaps lesson: most values sit near the bottom and barely move, so it costs O(n).

The second loop does the sorting. The root is the largest value in the heap, so swap it with the heap's last value: it now sits where it belongs, since nothing left in the heap is larger. Shrink the heap by one, so that cell is never touched again. The value that came up to the root was a leaf, usually small, so it sinks back down, swapping with its larger child.

A heap of n values is about log₂ n levels deep, and a sift-down makes at most two comparisons per level: one to find the larger child, one to compare it with the sinking value. So the n − 1 passes cost O(n log n), whatever the order of the input.

Sift-down is a loop, not a recursion, and every move is a swap inside the array, so there is no call stack to grow and no buffer. Quick sort can't promise the time, and even a careful one keeps O(log n) calls on its stack; merge sort needs the buffer. Here are heap sort and quick sort on sorted lists, quick sort's worst order:

At n = 64 quick sort makes about 1,200 comparisons and heap sort about 590. Doubling n from 32 multiplies quick sort's count by about 3.4 and heap sort's by about 2.5, close to the 2.4 of n log₂ n.

Before each step, predict whether the sinking value swaps with its larger child. It swaps only if that child is strictly larger: the test in the code panel is A[c] ≤ A[i]: stop. This list holds two 81s, so one prediction is a tie; watch where each 81 ends up.

Here is the second loop on its own, on five values that already form a max-heap: 9 above 7 and 8, and 7 above 2 and 5. Each pass swaps the root with nums[end], sifts the new root down through the end values still in the heap, and prints the array.

def sift_down(a, i, size):
    while 2 * i + 1 < size:
        c = 2 * i + 1
        if c + 1 < size and a[c + 1] > a[c]:
            c += 1
        if a[c] <= a[i]:
            return
        a[i], a[c] = a[c], a[i]
        i = c

nums = [9, 7, 8, 2, 5]
for end in range(len(nums) - 1, 0, -1):
    nums[0], nums[end] = nums[end], nums[0]
    sift_down(nums, 0, end)
    print(*nums)

The whole sort puts the build in front: a sift-down over the whole array, size n, for each parent from ⌊n/2⌋ − 1 down to 0. Notice which heap it builds to sort smallest first.

Does a sorted input help, as it helps insertion sort? Here are the 12 sorted values that cost quick sort 66 comparisons in its lesson.

47 to 55 comparisons in three orders, where quick sort's ranged from 35 to 66. The order mostly changes the cheap build: each pass of the second loop brings up a value from the bottom of the heap, usually small, which sinks most of the way back whatever the order.

The long swaps cost something else. In the Predict run, the 81 that started at position 1 was the first root swapped to the end and finished last, behind the 81 from position 3.

On the random order heap sort made 53 comparisons, and quick sort 35 on the same values. A better worst case doesn't make a faster sort.

• Heap sort builds a max-heap in the array bottom-up, in O(n), then n − 1 times swaps the root into the last cell of the heap, shrinks the heap by one and sifts the new root down.
• The sorted part grows from the right; the part on the left is a heap, never a sorted list.
• Each sift-down walks at most about log₂ n levels, so heap sort is O(n log n) on every input, with O(1) extra memory and no recursion.
• To sort smallest first in place, build a max-heap: each pass fills the last cell of the heap, where the largest value left belongs.
• It is not stable, and more comparisons and scattered memory reads make it slower than quick sort, so introsort keeps it as a fallback.
• Next: sorting without comparisons, where counting sort and radix sort can beat n log n, and Comparison budget, which shows why no comparison sort can. Make each swap yourself in Be the algorithm, practise with Smash the Heaviest Stones, Kth Largest Number in a List and Closest Points to the Origin, or open the heap sort visualiser.