Tracing the Complete Sort

We run heapSort on our array, [5, 3, 8, 1, 9, 2]. As in the earlier traces, i marks the value that is sinking, and the shaded slots are the finished tail.

buildHeap

n is 6, so the loop sinks index 2, then index 1, then index 0:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 9 │ 2 │
└───┴───┴───┴───┴───┴───┘

Index 2 holds 8. Its only child is 2, at index 5. 8 is not smaller than 2, so 8 stays.

Index 1 holds 3. Its children are 1 and 9. The larger is 9, and 3 is smaller, so they swap. Index 4 is a leaf, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 9 │ 8 │ 1 │ 3 │ 2 │
└───┴───┴───┴───┴───┴───┘
                  ↑
                  i

Index 0 holds 5. Its children are 9 and 8. The larger is 9, and 5 is smaller, so they swap:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 9 │ 5 │ 8 │ 1 │ 3 │ 2 │
└───┴───┴───┴───┴───┴───┘
      ↑
      i

5 is at index 1 now. Its children are 1 and 3. The larger is 3, and 5 is not smaller, so the sink stops. The array is a max-heap: every node is no smaller than its children.

sortdown

end starts at 5. Swap the root, 9, to index 5. The heap is now the first five slots:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 2 │ 5 │ 8 │ 1 │ 3 │░9░│   size = 5
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 2. Its children are 5 and 8. The larger is 8, so they swap. The children of index 2 would be at indices 5 and 6, outside the heap, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 8 │ 5 │ 2 │ 1 │ 3 │░9░│   size = 5
└───┴───┴───┴───┴───┴───┘
          ↑
          i

end is 4. Swap the root, 8, to index 4:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 5 │ 2 │ 1 │░8░│░9░│   size = 4
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 3. Its children are 5 and 2. The larger is 5, so they swap. At index 1, the only child inside the heap is 1, at index 3, and 3 is not smaller, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 3 │ 2 │ 1 │░8░│░9░│   size = 4
└───┴───┴───┴───┴───┴───┘
      ↑
      i

end is 3. Swap the root, 5, to index 3:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 2 │░5░│░8░│░9░│   size = 3
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 1. Its children are 3 and 2. The larger is 3, so they swap. The children of index 1 would be at indices 3 and 4, outside the heap, so the sink stops:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 3 │ 1 │ 2 │░5░│░8░│░9░│   size = 3
└───┴───┴───┴───┴───┴───┘
      ↑
      i

end is 2. Swap the root, 3, to index 2:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 2 │ 1 │░3░│░5░│░8░│░9░│   size = 2
└───┴───┴───┴───┴───┴───┘
  ↑
  i

Sink 2. Its only child is 1, and 2 is not smaller, so 2 stays.

end is 1. Swap the root, 2, with index 1, which holds 1. The heap is down to one element, 1, and it is already in place. The loop ends, and the array is sorted:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 5 │ 8 │ 9 │
└───┴───┴───┴───┴───┴───┘