Heap Sort
- Ω( n log n )
- Θ( n log n )
- O( n log n )
- space O( 1 )
Array
Comparator strip
Index down, time to the right
- Comparisons count only element-against-element checks; loop and index checks are never counted.
- Reads and writes include reads and writes to helper buffers (merge, counting, radix, bucket and tim sort).
- A swap counts once, as a swap. It is never also counted as a read or a write.
- Real time is the average time of the counted sort on this device over repeated runs, measured once before playback and independent of animation speed. Visual time is the time spent animating, excluding pauses.
How heap sort works
Heap sort first arranges the array into a binary max-heap, where every parent is at least as large as its children. It then repeatedly swaps the root, the largest element, to the end of the array and restores the heap on what remains.
Read more
It is an improved selection sort: the heap finds the next maximum in O(log n) instead of scanning. It sorts in place with a guaranteed O(n log n) time, but its memory access pattern jumps around, so it is usually slower than quick sort in practice.
| Best time | Ω( n log n ) | good |
|---|---|---|
| Average time | Θ( n log n ) | good |
| Worst time | O( n log n ) | good |
| Worst space | O( 1 ) | good |
Big O notation gives the lower, average and upper bounds of an algorithm. Time complexity bounds the number of operations; space complexity bounds the extra memory it uses.