Heap Sort
Build a max-heap in place, then repeatedly swap the root to the end of the shrinking heap and sift the new root down.
Heap Sort: Eight values
Index 3 holds 5. Its larger child is 2 at index 7. 5 is already at least as large, so the heap property holds here.
Cost
- Best
- O(n log n)
- Average
- O(n log n)
- Worst
- O(n log n)
- Space
- O(1)
Properties
- Yes: Comparison based
- No: Stable
- Yes: In place
- No: Adaptive
- No: Online
Before this
Related
Leads to
Topics that need this one first.