Heapsort

The result of the previous section suggests yet another algorithm for sorting. Given n items, we insert them into a Heap and then remove them. Because of the Heap semantics, they come out in order. We have already shown that this algorithm, which is called heapsort, takes time proportional to n log₂ n, which is better than selection sort and the same as mergesort.

As the value of n gets large, we expect heapsort to be faster than selection sort, but performance analysis gives us no way to know whether it will be faster than mergesort. We would say that the two algorithms have the same order of growth because they grow with the same functional form. Another way to say the same thing is that they belong to the same complexity class.

Complexity classes are sometimes written in "big-O notation". For example, O(n²), pronounced "oh of en squared" is the set of all functions that grow no faster than n² for large values of n. To say that an algorithm is O(n²) is the same as saying that it is quadratic. The other complexity classes we have seen, in decreasing order of performance, are:

So far none of the algorithms we have looked at are exponential. For large values of n, these algorithms quickly become impractical. Nevertheless, the phrase "exponential growth" appears frequently in even non-technical language. It is frequently misused so I wanted to include its technical meaning.

People often use "exponential" to describe any curve that is increasing and accelerating (that is, one that has positive slope and curvature). Of course, there are many other curves that fit this description, including quadratic functions (and higher-order polynomials) and even functions as undramatic as n log n. Most of these curves do not have the (often detrimental) explosive behavior of exponentials.

As an exercise, compare the behavior of 1000 n² and 2ⁿ as the value of n increases.