Heap Sort

Build a max-heap in O(n), then repeatedly extract the maximum and place it at the end. Guaranteed O(n log n) with O(1) space.

HEAP-SORT(A):
  n = length(A)

  // Phase 1: Build max-heap (bottom-up)
  FOR i = floor(n/2)-1 DOWNTO 0:
    HEAPIFY(A, n, i)

  // Phase 2: Extract elements one by one
  FOR i = n-1 DOWNTO 1:
    SWAP(A[0], A[i])     // move max to end
    HEAPIFY(A, i, 0)     // restore heap on reduced array

HEAPIFY(A, size, root):
  largest = root
  left  = 2*root + 1
  right = 2*root + 2

  IF left < size AND A[left] > A[largest]:
    largest = left
  IF right < size AND A[right] > A[largest]:
    largest = right

  IF largest != root:
    SWAP(A[root], A[largest])
    HEAPIFY(A, size, largest)  // fix subtree