Heap Sort

Rearrange the array into a max-heap, then repeatedly swap the root to the end and sift down. O(n log n) in the worst case like merge sort, but in O(1) space — the heap lives inside the array itself.

time O(n log n) always

space O(1)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

build-max-heap(a)
for end in n-1 down to 1:
  swap(a[0], a[end])
  sift-down(a, 0, end)