Heap Sort

#Computers

$\displaystyle O(\log n)$

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