Heapsort – Conclusion

• the initial tree can be created in O(n) steps

• taking the element at the top and inserting one from the bottom needs O(log n) steps, this is done n times, once for each element

• therefore Heapsort can sort a list with n elements in O(n log n) steps