Heap sort on 37, 33, 26, 92, ...

Heap sort has two phases: (1) build a max-heap from the list, (2) repeatedly remove the largest element and put it at the end.

Algorithm

HeapSort(a[0..n-1])
1. for i = n/2 - 1 down to 0: Sift(a, i, n)       /* build max-heap */
2. for last = n-1 down to 1:
      swap a[0] and a[last]                       /* max goes to its place */
      Sift(a, 0, last)                            /* heap size is now 'last' */

Sift(a, i, n):   /* push a[i] down until parent >= children */
   while 2i+1 < n:
       c = index of larger child of i
       if a[c] <= a[i] stop
       swap a[i], a[c]; i = c

Phase 1: build the heap

List (index 0 to 11): 37, 33, 26, 92, 57, 18, 48, 25, 12, 86, 42, 22. The last parent is index 5 (n/2 − 1).

Heap obtained:

level 0:  92
level 1:  86   48
level 2:  33   57   22   26
level 3:  25   12   37   42   18

Phase 2: sorting

Each pass swaps the root with the last heap element, shrinks the heap by one, and sifts the root down.

Sorted list: 12, 18, 22, 25, 26, 33, 37, 42, 48, 57, 86, 92

Complexity: building O(n), n − 1 sift-downs of O(log n) each, so O(n log n) overall.