Heapsort

The heapsort is a sorting algorithm using max-heap data structure. It basically works like this:

1. Divides the input into a sorted and an unsorted region.
2. Takes the largest element from the unsorted region and inserts it into the sorted region.
3. The unsorted region is kept as a heap, which allows finding the largest element quickly.

Complexity

Time complexity

• Worst-case: $O(n\log n)$

Resources

• Heapsort visualization – David Galles
• Heapsort in 4 minutes – Youtube