Heap Sort: Analysis

• Creating the heap takes ?(n) time.

• The sort portion is Obviously O(nlgn)

• A more careful analysis would show an exact time bound of ?(nlgn)

• Average and worst case are the same

• The algorithm runs in place

Previous slide

Next slide

Back to first slide

View graphic version