HeapSort Trace

Problem: sort int[] list = {?, 3, 1, 4, 5, 9, 2, 6, 8, 0, 7}

Heapsort sorts, in place, using an array for both the data and the heap. The boundary between the two goes back and forth. At first it's all unordered list, then all heap, then back to list, but ordered. The trace show the state of the array after each number is processed. (The 1st element of the array is not used.)

Suggested Exercise: Sketch the heap at various points in the process. 


   |---|---|---|---|---|---|---|---|---|---|---|
   |_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|_10|
   |   # 3 | 1 | 4 | 5 | 9 | 2 | 6 | 8 | 0 | 7 | all unsorted list
   |   | 3 # 1 | 4 | 5 | 9 | 2 | 6 | 8 | 0 | 7 |
  1|   | 3 # 1 | 4 | 5 | 9 | 2 | 6 | 8 | 0 | 7 |
   |   | 3 | 1 # 4 | 5 | 9 | 2 | 6 | 8 | 0 | 7 |
  2|   | 3 | 1 # 4 | 5 | 9 | 2 | 6 | 8 | 0 | 7 |
   |   | 3 | 1 | 4 # 5 | 9 | 2 | 6 | 8 | 0 | 7 |
  3|   | 4 | 1 | 3 # 5 | 9 | 2 | 6 | 8 | 0 | 7 |
   |   | 4 | 1 | 3 | 5 # 9 | 2 | 6 | 8 | 0 | 7 |
  4|   | 5 | 4 | 3 | 1 # 9 | 2 | 6 | 8 | 0 | 7 |
   |   | 5 | 4 | 3 | 1 | 9 # 2 | 6 | 8 | 0 | 7 |
  5|   | 9 | 5 | 3 | 1 | 4 # 2 | 6 | 8 | 0 | 7 |
   |   | 9 | 5 | 3 | 1 | 4 | 2 # 6 | 8 | 0 | 7 |
  6|   | 9 | 5 | 3 | 1 | 4 | 2 # 6 | 8 | 0 | 7 |
   |   | 9 | 5 | 3 | 1 | 4 | 2 | 6 # 8 | 0 | 7 |
  7|   | 9 | 5 | 6 | 1 | 4 | 2 | 3 # 8 | 0 | 7 |
   |   | 9 | 5 | 6 | 1 | 4 | 2 | 3 | 8 # 0 | 7 |
  8|   | 9 | 8 | 6 | 5 | 4 | 2 | 3 | 1 # 0 | 7 |
   |   | 9 | 8 | 6 | 5 | 4 | 2 | 3 | 1 | 0 # 7 |
  9|   | 9 | 8 | 6 | 5 | 4 | 2 | 3 | 1 | 0 # 7 |
   |   | 9 | 8 | 6 | 5 | 4 | 2 | 3 | 1 | 0 | 7 #
 10|   | 9 | 8 | 6 | 5 | 7 | 2 | 3 | 1 | 0 | 4 # all max heap
   |---|---|---|---|---|---|---|---|---|---|---|
   |_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|_10|
   |   | 9 | 8 | 6 | 5 | 7 | 2 | 3 | 1 | 0 | 4 # all max heap
   |   | 4 | 8 | 6 | 5 | 7 | 2 | 3 | 1 | 0 # 9 |
  1|   | 8 | 7 | 6 | 5 | 4 | 2 | 3 | 1 | 0 # 9 |
   |   | 0 | 7 | 6 | 5 | 4 | 2 | 3 | 1 # 8 | 9 |
  2|   | 7 | 5 | 6 | 1 | 4 | 2 | 3 | 0 # 8 | 9 |
   |   | 0 | 5 | 6 | 1 | 4 | 2 | 3 # 7 | 8 | 9 |
  3|   | 6 | 5 | 3 | 1 | 4 | 2 | 0 # 7 | 8 | 9 |
   |   | 0 | 5 | 3 | 1 | 4 | 2 # 6 | 7 | 8 | 9 |
  4|   | 5 | 4 | 3 | 1 | 0 | 2 # 6 | 7 | 8 | 9 |
   |   | 2 | 4 | 3 | 1 | 0 # 5 | 6 | 7 | 8 | 9 |
  5|   | 4 | 2 | 3 | 1 | 0 # 5 | 6 | 7 | 8 | 9 |
   |   | 0 | 2 | 3 | 1 # 4 | 5 | 6 | 7 | 8 | 9 |
  6|   | 3 | 2 | 0 | 1 # 4 | 5 | 6 | 7 | 8 | 9 |
   |   | 1 | 2 | 0 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
  7|   | 2 | 1 | 0 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
   |   | 0 | 1 # 2 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
  8|   | 1 | 0 # 2 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
   |   | 0 # 1 | 2 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
  9|   | 0 # 1 | 2 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
   |   # 0 | 1 | 2 # 3 | 4 | 5 | 6 | 7 | 8 | 9 |
   |---|---|---|---|---|---|---|---|---|---|---|  all sorted list
   |_0_|_1_|_2_|_3_|_4_|_5_|_6_|_7_|_8_|_9_|_10|