Heapsort
Arranges the list into a heap, a tree where every parent is bigger than its children. Then it moves the biggest value to the end, again and again.
- best Ω(n log n)
- average Θ(n log n)
- worst O(n log n)
- space O(1)
- not stable
- in place
What do these mean?
- Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
- Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
- Worst case: the growth on the hardest input. Useful when speed must never drop.
- Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
- Stable: two equal values keep their original order. Matters when sorting by one field of a record.
- In place: sorts inside the list itself, with no second list.
- comparing
- moving
- in final place
Press play: the lines show how the cost grows as the sort runs
Press play or step through the algorithm.
Space: play or pause. Left and right arrows: step. Home and End: jump.
Try this: Pick a reversed list. Building the heap takes almost no swaps, then every round moves the biggest value to the end.
How it works
The heap is stored in the list itself: the value at position i has its children at positions 2i+1 and 2i+2, and the biggest value is always at the front. Swap it to the end, make the heap one smaller and repair it. The sorted part grows from the right.
When it is a good choice
When you need speed that stays good even in the worst case and no extra memory, for example on small devices. On average it is slower than quicksort, so it is often used as a safety net.