Skip to content
Back to AlgorithmsAll lessons

Algorithms

Heap Sort

O(n log n) time — every item moves down roughly log n levels · O(1) space, since it sorts in place.

The idea, in plain English

Heap sort works like a tournament bracket. You arrange everyone so every 'parent' is bigger than their 'children'. This shape is called a heap, and it always pushes the biggest player to the very top. Take the champion off the top and place it at the end of your sorted list. Let the next-biggest rise to the top, then repeat.

How it works

  1. 1Arrange the whole list into a max heap, a shape where the largest item sits at the root (index 0).
  2. 2Swap the root with the last unsorted item. This puts the current largest item in its final sorted spot.
  3. 3Shrink the heap by one item, then 'heapify' — fix the heap shape — starting from the root. Repeat until nothing is left to sort.

When you'd use it

Use it when you need guaranteed O(n log n) sorting without merge sort's extra memory. Heap sort sorts in place. Heaps also power priority queues directly.

Common beginner mistakes

  • Getting the child index formulas wrong. A node at index i has children at index 2i+1 and 2i+2.
  • Forgetting to re-heapify after swapping the root. This leaves the heap shape broken for the rest of the sort.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Before: 5 2 9 1 5 6
Sorted: 1 2 5 5 6 9

See it in motion

Watch it sortHeap sortO(n log n) time — every item moves down roughly log n levels · O(1) space, since it sorts in place.

Ready. Press play to watch it sort.

0
Comparisons
0
Writes
0/32
Step
0.0s
Time
ComparingSwappingSorted

Not sure this is the right topic? See the learning paths → or where this leads →