Heap Sort

#programming #algorithms

Read Heap for background.

Heap sort uses a max-heap, to maintain ascending order.

Steps :

1. Build max heap ($O(n)$)
2. Swap root with last element
3. Reduce heap size by popping last element (effective extraction)
4. Heapify root
5. Repeat

Time complexity : $O(n\log n)$