Heap Sort

Why Ascending Heap Sort Uses a Max-Heap

If you built a min-heap at a[0 .. n - 1], popping the minimum a[0] would force you to shift the rest of the heap or allocate a second array.

Instead, Heap Sort builds a Max-Heap right inside nums:

1. Phase 1 — Build Max-Heap in O(n): Every leaf (index >= n // 2) already satisfies the max-heap invariant (parent >= children). Starting at the last internal node n // 2 - 1 and walking backward to 0, sift_down repairs subtrees bottom-up in linear O(n) total work.
2. Phase 2 — Extract Maximums into the Tail (O(n log n)): For end from n - 1 down to 1:
   • Swap the max root nums[0] with nums[end]. Slot end now holds its final sorted value!
   • Shrink the active heap boundary to [0 .. end - 1] and call sift_down(0, end - 1) in O(log n) to float the next maximum to nums[0].

Clean In-Place Python Implementation

def sift_down(nums: list[int], root: int, end: int) -> None:
    """Restore max-heap order on nums[root .. end] inclusive in O(log n)."""
    idx = root
    while 2 * idx + 1 <= end:
        left = 2 * idx + 1
        right = left + 1
        largest = idx

        if nums[left] > nums[largest]:
            largest = left
        if right <= end and nums[right] > nums[largest]:
            largest = right

        if largest == idx:
            return

        nums[idx], nums[largest] = nums[largest], nums[idx]
        idx = largest


def heap_sort(nums: list[int]) -> list[int]:
    """In-place Heap Sort: worst-case O(n log n) time, O(1) auxiliary space."""
    n = len(nums)

    # Phase 1: Floyd's O(n) bottom-up max-heap construction
    for start in range(n // 2 - 1, -1, -1):
        sift_down(nums, start, n - 1)

    # Phase 2: Repeatedly lock max root into nums[end] and repair heap
    for end in range(n - 1, 0, -1):
        nums[0], nums[end] = nums[end], nums[0]
        sift_down(nums, 0, end - 1)

    return nums

Trade-Offs vs. Merge Sort & Quicksort