Heap Sort

$O(\log n)$

• Puts elements from the array into a heap structure in $O(n\log n)$ time
• Extracts the root of the heap into an array until the heap is empty in $O(n\log n)$ time