Sifting Down Past the End of the Heap

A heapsort whose extraction phase sifts down within the whole array, instead of stopping at the boundary of the heap, returns an array that is not sorted, because the sift-down reaches the sorted items and pulls them back into the heap. This card shows the symptom, the trigger, why it happens, what it costs and the fix.

The symptom is output that looks partly sorted, or not sorted at all, often with the largest items back near the front. The code runs without an error and the heap phase looks right, so the bug hides in plain sight.

The trigger is reusing the sift-down from the build with the same bound. The build sifts within the whole array, so its bound is the array's length. Each extraction must sift only within the heap, which shrinks by one item every time. The listing below runs one heapsort on 9 7 8 4 5 2 with the bound set to the array's length, and one with the bound set to end, and prints the array after the first extraction and at the end of each.

def sift_down(items, i, end):
    while 2 * i + 1 < end:
        child = 2 * i + 1
        if child + 1 < end and items[child + 1] > items[child]:
            child += 1
        if items[i] >= items[child]:
            return
        items[i], items[child] = items[child], items[i]
        i = child


def heapsort(items, bound_is_length):
    n = len(items)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(items, i, n)
    for end in range(n - 1, 0, -1):
        items[0], items[end] = items[end], items[0]
        sift_down(items, 0, n if bound_is_length else end)
        if end == n - 1:
            print("  after the first extraction:", " ".join(map(str, items)))
    print("  at the end:", " ".join(map(str, items)))


for label, flag in (("bound len(items)", True), ("bound end", False)):
    print(label)
    heapsort([9, 7, 8, 4, 5, 2], flag)

bound len(items)
  after the first extraction: 8 7 9 4 5 2
  at the end: 9 8 7 4 5 2
bound end
  after the first extraction: 8 7 2 4 5 9
  at the end: 2 4 5 7 8 9

The mechanism shows in the first extraction. The root, 9, is swapped with 2 at index 5, which leaves 2 7 8 4 5 9 and the heap at indices 0 to 4. With the length as bound, the sift-down still counts index 5 as part of the heap. It swaps 2 with 8, its larger child, then finds that 2 at index 2 has a child at index 5, 9, which is larger, and swaps again. The largest item, already in its final place, is back inside the heap, and the array is 8 7 9 4 5 2. Every later extraction does the same to the items placed before it, and the run ended on 9 8 7 4 5 2, close to the reverse of sorted.

The cost is a wrong answer rather than a slow one. Nothing raises an error, so the half-sorted array reaches whatever reads it next, and the fault surfaces far from the sort.

The remedy is to pass the boundary, highlighted on line 18. After swapping the root into index end, the heap is indices 0 to end − 1, so end is the bound, and the sift-down stops before the sorted part. A check against the language's built-in sort, which every listing in this topic makes, catches the bug on the first run.