Heapsort

Heapsort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements.

Time Complexity: O(n log n)

Space Complexity: O(1)

build max heap from array
for i from n-1 down to 1:
  swap(arr[0], arr[i])
  heapify(arr, 0, i)