Heap Sort

Algorithm

1. First establish a heap tree from a list, by starting with the first element in the list and then appending the elements from the list as leaves. Each time when a node is added, make sure to perform the necessary swaps so that nodes with higher values trickle to the top of the heap.
2. Write the numbers back to the list starting from the top-most node and going from left to right.
3. Exchange the root of the tree with the lower right-most leaf (or left leaf, if the right-most leaf does not exist), performing the same swap in the list, and delete it from the tree. After that, make sure to let the higher value leaves trickle up. Repeat the same process until all the leaves have been removed.

Performance

• Worst case:
• Best case:
• Average case:
• Space complexity: total or auxiliary