AlgoScope

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.

Sorting, algorithm, intermediate
Parent 5 at 3, larger child 2 at 7. Stop.heap 0-740101325314857627ichild2 < 5
Parent 5 at 3, larger child 2 at 7. Stop.heap 0-740101325314857627ichild2 < 5

Heap Sort: Eight values

Decision, step 2 of 26

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

Leads to

Topics that need this one first.