Heap sort

O(n log n)

Heap sort treats the array as a binary heap. It first rearranges it into a max-heap (every parent ≥ its children), then repeatedly swaps the root (the maximum) to the end of the unsorted region and sifts the new root down to restore the heap. It runs in O(n log n) in the worst case and sorts in place, with no recursion.

Array
Edit the input and press Play

How it works

  1. Build a max-heap so the largest value sits at the root (index 0).
  2. Swap the root with the last unsorted element — the max is now in place.
  3. Sift the new root down to repair the heap property.
  4. Shrink the heap by one and repeat until it is empty.

Pseudocode

1heapSort(a):                        # O(n log n)2  build a max-heap from a3  for end from n-1 down to 1:4    swap(a[0], a[end])               # max → its final spot5    siftDown(a, 0, end-1)           # restore the heap