Lower Bounds For Sorting

Lower bounds for sorting: In a comparison sort, we use only comparisons between elements to gain order information about an input sequence 〈a₁, a₂, . . ., a_n〉. That is, given two elements a_i and a_j, we perform one of the tests a_i < a_j, a_i ≤ a_j, a_i = a_j, a_i ≥ a_j, or a_i > a_j to determine their relative order. We may not inspect the values of the elements or gain order information about them in any other way.

In this section, we assume without loss of generality that all of the input elements are distinct. Given this assumption, comparisons of the form a_i = a_j are useless, so we can assume that no comparisons of this form are made. We also note that the comparisons a_i ≤ a_j, a_i ≥ a_j, a_i > a_j, and a_i < a_j are all equivalent in that they yield identical information about the relative order of a_i and a_j. We therefore assume that all comparisons have the form a_i ≤ a_j.

The decision-tree model: Comparison sorts can be viewed abstractly in terms of decision trees. A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size. Control, data movement, and all other aspects of the algorithm are ignored. Figure 8.1 shows the decision tree corresponding to the insertion sort algorithm from Section 2.1 operating on an input sequence of three elements.

Figure 8.1: The decision tree for insertion sort operating on three elements. An internal node annotated by i: j indicates a comparison between a_i and a_j. A leaf annotated by the permutation 〈π(1), π(2), . . ., π(n)〉 indicates the ordering a_π(1) ≤ a_π(2) ≤ ··· a_π(n). The shaded path indicates the decisions made when sorting the input sequence 〈a₁ = 6, a₂ = 8, a₃ = 5〉 the permutation 〈3, 1, 2〉 at the leaf indicates that the sorted ordering is a₃ = 5 a₁ = 6 a₂ = 8. There are 3! = 6 possible permutations of the input elements, so the decision tree must have at least 6 leaves.

In a decision tree, each internal node is annotated by i: j for some i and j in the range 1 ≤ i, j n, where n is the number of elements in the input sequence. Each leaf is annotated by a permutation 〈π(1), π(2), . . ., π(n)〉. The execution of the sorting algorithm corresponds to tracing a path from the root of the decision tree to a leaf. At each internal node, a comparison a_i a_j is made. The left subtree then dictates subsequent comparisons for a_i a_j, and the right subtree dictates subsequent comparisons for a_i > a_j. When we come to a leaf, the sorting algorithm has established the ordering a_π(1) a_π(2) ··· a_π(n). Because any correct sorting algorithm must be able to produce each permutation of its input, a necessary condition for a comparison sort to be correct is that each of the n! permutations on n elements must appear as one of the leaves of the decision tree, and that each of these leaves must be reachable from the root by a path corresponding to an actual execution of the comparison sort. (We shall refer to such leaves as "reachable.") Thus, we shall consider only decision trees in which each permutation appears as a reachable leaf.

A lower bound for the worst case: The length of the longest path from the root of a decision tree to any of its reachable leaves represents the worst-case number of comparisons that the corresponding sorting algorithm performs. Consequently, the worst-case number of comparisons for a given comparison sort algorithm equals the height of its decision tree. A lower bound on the heights of all decision trees in which each permutation appears as a reachable leaf is therefore a lower bound on the running time of any comparison sort algorithm. The following theorem establishes such a lower bound.

Any comparison sort algorithm requires Ω(n lg n) comparisons in the worst case.

Proof From the preceding discussion, it suffices to determine the height of a decision tree in which each permutation appears as a reachable leaf. Consider a decision tree of height h with l reachable leaves corresponding to a comparison sort on n elements. Because each of the n! permutations of the input appears as some leaf, we have n! ≤ l. Since a binary tree of height h has no more than 2^h leaves, we have

n! ≤ l 2^h,

which, by taking logarithms, implies

h	≤	lg(n!)	(since the lg function is monotonically increasing)
	=	Ω(n lg n)