How Heapsort Works

The heap_size parameter is the key design choice in this signature. By accepting the boundary as an argument rather than using len(unsorted) directly, the function can operate on a shrinking region of the same list during the extraction phase. That is what makes heapsort in-place: the sorted elements accumulate at the back of the array while heap_size decreases, and heapify never touches the sorted suffix. The two-step doctest makes the sift-down visible. Starting from [1, 4, 3, 5, 2], the first call finds 1 at the root is smaller than its children (4 and 3), so it swaps 1 down and the root becomes 4; a second heapify is needed because 4 is smaller than 5. After two calls the heap root holds the maximum value.

A binary heap stored in a list places the left child of node at index i at index 2i+1 and the right child at 2i+2. That is the only formula this function needs to navigate the heap. Lines 21 and 22 compute both child indices. Lines 23 and 26 each check whether the child exists (index within heap_size) and whether it is larger than the current candidate for the largest position. After both checks, largest points to whichever of the three nodes (current, left child, right child) holds the maximum value. If that is not the root, line 30 swaps the root and the larger child, then line 31 recurses downward. The recursion terminates when the node is already the largest in its subtree or when it reaches a leaf. Each level of the heap has at most one comparison, so heapify costs O(log n).

The four doctests cover duplicates, the empty list, negative values, and an eleven-element mixed list including both a very large and a very small integer. The build phase on lines 51 through 53 is Robert W. Floyd's O(n) improvement. The loop starts at n//2 - 1, which is the index of the last non-leaf node in a zero-indexed binary heap. Leaf nodes (indices from n//2 to n-1) are already trivially valid heaps of size one, so heapifying them would be wasted work. Going from n//2-1 down to 0 ensures that when heapify is called at any index, both its children already satisfy the heap property, so the sift-down finds the correct position in O(log n) passes. The total build cost is O(n) because most nodes are near the bottom of the tree and their sift paths are short.

After the build phase, unsorted[0] holds the maximum element of the entire array. The extraction loop swaps it to position i (the last unsorted position), then calls heapify(unsorted, 0, i) with the heap size reduced by one. That i in the heapify call is what keeps the freshly placed maximum out of the heap: heapify never considers indices at or beyond its heap_size argument. After n-1 iterations the loop ends when only one element remains at index 0, and since every larger element has already been placed at its correct position, the full array is sorted ascending. The sorted elements grow from right to left; no extra memory is allocated. Each iteration costs O(log i), and summing from i = n-1 down to 1 gives O(n log n) total.

Two details here differ from the bubble_sort.py and merge_sort.py drivers. First, the import of doctest is deferred inside the if __name__ block rather than at the top of the file, which keeps the module lighter when it is imported rather than run directly. Second, the input is guarded by if user_input: on line 65, so pressing Enter without typing anything exits cleanly instead of producing a ValueError from int(item) on an empty string. The print(f"{heap_sort(unsorted) = }") idiom on line 67 uses Python's debug f-string format (= suffix), which prints both the expression and its value as heap_sort(unsorted) = [...]. That is more informative than a bare print when a contributor is checking output during development.