Heapsort

Heapsort is a comparison sort that uses a binary heap to repeatedly extract the maximum. It runs in O(n log n) time, in place, with O(1) extra space — the only mainstream comparison sort with all three properties.

Complexity

How it works

First, heapify the array into a max-heap in O(n). Then repeatedly: swap the root (largest element) with the last element of the heap, shrink the heap by one, and sift the new root down. After n iterations the array is sorted ascending.

Python implementation

def heapsort(arr):
    """In-place heapsort using a max-heap."""
    n = len(arr)

    def sift_down(start, end):
        root = start
        while 2 * root + 1 < end:
            child = 2 * root + 1
            if child + 1 < end and arr[child] < arr[child + 1]:
                child += 1
            if arr[root] < arr[child]:
                arr[root], arr[child] = arr[child], arr[root]
                root = child
            else:
                return

    for start in range(n // 2 - 1, -1, -1):
        sift_down(start, n)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end)
    return arr


print(heapsort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

Trade-offs

• In-place, O(1) auxiliary memory.
• Guaranteed O(n log n) — no quicksort-style worst case.
• Not stable.
• Slower than quicksort in practice due to poor cache locality (jumps around the heap).

← Back to Algorithms