Heap Sort

pseudocode

heapify(a, i, size):
  left = 2*i + 1; right = 2*i + 2
  largest = maxIndex(i, left, right)
  if largest != i:
    swap a[i], a[largest]
    heapify(a, largest, size)
heapSort(a):
  buildMaxHeap: heapify all non-leaf nodes
  for i from n-1 down to 1:
    swap a[0], a[i]; heapify(a, 0, i)