Tracing Heapsort

In-place heapsort sorts an array in ascending order in two phases.

• buildHeap rearranges the array into a max-heap. It reads the array as a tree in level order, where the children of index $i$ are at $2i+1$ and $2i+2$. Then it sinks each internal node, from the last one back to the root. A sink swaps the value with its larger child until the value is no smaller than its children or has no children.
• sortdown empties the heap. In each turn it swaps the root with the last slot of the heap, shrinks the heap by one so that slot is no longer part of it, and sinks the new root within the smaller heap. It stops when one element is left.

The questions in this section sort this array:

   0    1    2    3    4    5    6
┌────┬────┬────┬────┬────┬────┬────┐
│ 40 │ 70 │ 20 │ 90 │ 10 │ 60 │ 30 │
└────┴────┴────┴────┴────┴────┴────┘

start                               [40, 70, 20, 90, 10, 60, 30]
sink index 2 (20↔60)                [40, 70, 60, 90, 10, 20, 30]
sink index 1 (70↔90)                [40, 90, 60, 70, 10, 20, 30]
sink index 0 (40↔90, then 40↔70)    [90, 70, 60, 40, 10, 20, 30]

start     [90, 70, 60, 40, 10, 20, 30]      size = 7
turn 1    [70, 40, 60, 30, 10, 20 | 90]     size = 6
turn 2    [60, 40, 20, 30, 10 | 70, 90]     size = 5
turn 3    [40, 30, 20, 10 | 60, 70, 90]     size = 4
turn 4    [30, 10, 20 | 40, 60, 70, 90]     size = 3
turn 5    [20, 10 | 30, 40, 60, 70, 90]     size = 2
turn 6    [10 | 20, 30, 40, 60, 70, 90]     size = 1