next up previous contents index Search
Next: Source Code Up: 0.3.3 Heapsort Previous: Operations on a Analysis

While the Heapsort is a constant factor slower than the Quicksort for average data sets, it still has a complexity of (n log2 n) for best, worst and average data. It also has some interesting properties that make it particularly useful for sorting data sets that are too large to fit into primary computer memory.

As we have seen, the initial heapification operation is a linear time complexity process. The push-down operation described is only a     variation of the heapify process. In the worst case 2i comparisons will be needed to fully demote a given node from the root to its proper place.

Scott Gasch