Heap Sort

Heap sort treats the array like a binary tree. Picture each slot as a node with two children further down the array, and a heap just means every parent sits above its children. Heap sort builds that arrangement first so the biggest value ends up at the very top, then it pulls that value off, parks it at the end, and lets the next biggest float up to take its place. Repeat until the heap is empty and the array is sorted from the back forward.

What I like about it is that it’s the steady one. It sorts in place with no extra array, and it never has a bad day: building the heap and draining it are both n log n no matter what you feed it, so sorted, reversed, or shuffled all cost about the same. Try the Sorted and Reversed inputs and watch the comparison count barely budge.

Hit Play to watch it run, or use Next and Back to step one comparison at a time. Shuffle deals a fresh array, and the highlighted line shows you where the code is at each step.