function heapsort(items):
   build_max_heap(items)

   for end from length(items) - 1 down to 1:
      swap(items, 0, end) # move current max to its final spot
      sift_down(items, 0, end) # restore heap in the shrinking prefix
   return items            # O(n log n), sorts in place
