Heapsort

Heapsort builds a max-heap and repeatedly extracts the largest element, giving guaranteed O(n log n) sorting in place.

Sort with a heap

Heapsort uses a binary heap to sort. First it rearranges the array into a max-heap so the largest element is at index 0. Then it repeatedly swaps the root to the end of the unsorted region and sifts the new root down, shrinking the heap by one each time. After n-1 extractions the array is sorted in ascending order.

Cost

Building the heap is O(n). Each of the n extractions costs O(log n) for the sift-down, so the extraction phase is O(n log n), which dominates. This bound holds in the best, average, and worst cases, giving heapsort a guaranteed O(n log n) with no bad inputs. It sorts in place with O(1) extra memory.

• Time: O(n log n) in all cases
• Extra space: O(1); in place
• Stable: no
• Not adaptive to existing order

def heap_sort(a):
    n = len(a)
    for i in range(n//2 - 1, -1, -1):
        sift_down(a, i, n)
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift_down(a, 0, end)

Why it is not stable

Heapsort moves elements across long distances during sift-down, so two equal keys can end up in reversed relative order. Making it stable would require extra bookkeeping that erases its in-place advantage, so in practice a stable O(n log n) sort means merge sort instead.

Where it fits

Heapsort combines the guaranteed worst case of merge sort with the in-place memory of quicksort, but its poor cache locality makes it slower than quicksort in practice, because each sift-down jumps between distant array indices that defeat the cache. Its main real-world role is as the fallback in introsort, ensuring quicksort's worst case can never actually materialise.