The Algorithm Design Manual Second Edition

4.7.1

Lower Bounds for Sorting

One last issue on the complexity of sorting. We have seen several sorting algorithms

that run in worst-case O(n log n) time, but none of which is linear. To sort n items

certainly requires looking at all of them, so any sorting algorithm must be Ω(n) in

the worst case. Can we close this remaining Θ(log n) gap?

The answer is no. An Ω(n log n) lower bound can be shown by observing that

any sorting algorithm must behave differently during execution on each of the dis-

tinct n! permutations of n keys. The outcome of each pairwise comparison governs

the run-time behavior of any comparison-based sorting algorithm. We can think of

the set of all possible executions of such an algorithm as a tree with n! leaves. The

minimum height tree corresponds to the fastest possible algorithm, and it happens

that lg(n!) = Θ(n log n).

This lower bound is important for several reasons. First, the idea can be ex-

tended to give lower bounds for many applications of sorting, including element

uniqueness, finding the mode, and constructing convex hulls. Sorting has one of

the few nontrivial lower bounds among algorithmic problems. We will present

an alternate approach to arguing that fast algorithms are unlikely to exist in

Chapter

9

.

---

4 . 8

W A R S T O R Y : S K I E N A F O R T H E D E F E N S E