Time complexity: O(n log n)
Heapsort is O(n log n) even in worst case scenario. It uses a heap data structure (tree). You build the tree by adding each new value to the end and then bubbling that value up if it is smaller that its parent (in the case of a min heap). You then repeatedly pop the root of the tree off to get sorted values. When you pop the root you then need to replace that root element with the last value in the tree. You then repeatedly swap with the smallest child until the child nodes are bigger than this node. Below are my whiteboard notes:
Due to the nature of a binary tree, we can use an array data structure to implement the heap. This works out easier than implementing a tree with node objects. We can use the following to calculate the array indexes:
left child index = i*2+1
right child index = i*2+2
parent index = (i-1)/2
Here is my c++ implementation of a Heap class and using it to do a heap sort:
https://gist.github.com/adamkorg/eb9324203e78617349db0f7eea04fbd2