Both of the sorting methods we have seen so far have a worst-case behavior of O(n2). It is natural at this point to ask the question, What is the best computing time for sorting that we can hope for? The theorem we shall prove shows’ that if we restrict our question to sorting algorithms in which the only operations permitted on keys are comparisons and interchanges, then O(n log n) is the best possible time.

The method we use is to consider a tree that describes the sorting process. Each vertex of the tree represents a key comparison, and the branches indicate the result. Such a tree is called a decision tree. A path through a decision tree represents a sequence of computations that an algorithm could produce.

**Example**

Let us look at the decision tree obtained for insertion sort working on a list with three records. The input sequence is Rlt R2• and R3• so the root of the tree is labeled (1. 2. 3). Depending on the. outcome of the comparison between keys K I and K 2. this sequence mayor may not change. If K 2 < K I. then the sequence becomes (2. 1. 3); otherwise it stays (1.2. 3). The full tree resulting from these comparisons is given.

The leaf nodes are labeled I to VI. These are the only points at which the algorithm may terminate. Hence, only six permutations of the input sequence are obtainable from this algorithm. Since all six of these are different, and 3! = 6, it follows that this algorithm has enough leaves to constitute a valid sorting algorithm for three records. The maximum depth of this tree is 3.It gives six different orderings of the key values 7, 9, and 10! which show that all six permutations are possible.

**Theorem: **Any decision tree that sorts n distinct elements has a height of at least log2(n !) + 1.

**Proof:** When sorting n elements, there are n ! different possible results. Thus, every decision tree for sorting must have at least n! leaves. But a decision tree is also a binary tree, which can have at most 2A:-1 leaves if its height is k. Therefore, the height must be at least log2 n !+ 1.

**Corollary:** Any algorithm that sorts only by comparisons must have a worst-case computing time of O(n log n).

Proof: We must show that for every decision tree with n! leaves, there is a path of length enlog2n, where c is a constant. By the theorem, there is a path of length log2n! .

Now

Using a similar argument and the fact that binary trees with 2″ leaves must have an average root-to-Ieaf path length of Ω(n log n). we can show that the average complexity of comparison-based sorting methods is Ω(n log n).