Heap sort

Problem¶

Implement in-place heap sort for a Python list.

Key trick¶

Build a max heap, repeatedly move its root to the end, and restore the heap.

Heap sort is inappropriate for linked lists because parent and child lookup requires efficient indexed access.

Trap¶

Heap construction is \(O(n)\), not \(O(n \log n)\), when performed bottom-up.

Why is it interesting?¶

It guarantees \(O(n \log n)\) time with \(O(1)\) auxiliary space, but it is unstable and generally slower than Python's built-in sort.

Python solution¶

class sort_heap_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]
        n = len(arr)

        # Build a max heap bottom-up in O(n) time.
        # Nodes after `n // 2 - 1` are leaves and need no work.
        for root in range(n // 2 - 1, -1, -1):
            self._sift_down(arr, root, n)

        # Repeatedly move the heap maximum to the sorted suffix.
        for end in range(n - 1, 0, -1):
            arr[0], arr[end] = arr[end], arr[0]

            # Exclude the newly sorted suffix from the heap.
            self._sift_down(arr, 0, end)

        return arr

    def _sift_down(
        self,
        arr: list[int],
        root: int,
        n: int,
    ) -> None:
        """Restore the max-heap property below `root`."""

        while True:
            # Array representation of a binary heap.
            l = 2 * root + 1
            r = l + 1
            largest = root

            # Find the largest among the root and its children.
            if l < n and arr[l] > arr[largest]:
                largest = l

            if r < n and arr[r] > arr[largest]:
                largest = r

            # The subtree already satisfies the heap property.
            if largest == root:
                return

            # Move the larger child up and continue down that subtree.
            arr[root], arr[largest] = arr[largest], arr[root]
            root = largest