The worst case complexity of any sorting algorithm that only uses key comparisons is

(*n*log
*n*)

**Result 2**

The average case complexity of any sorting algorithm that only uses key comparisons is

(*n*log
*n*)

The above results are proved using a Decision Tree which is a binary tree in which the nodes represent the status of the algorithm after making some comparisons.

Consider a node** ***x*** **in a decision tree and let**
***y*** **be its left child and zits right child. See Figure
**9.4.**

**Basically, ***y*** represents a state consisting of the information
known at
***x*** plus the fact that the key ***k*_{1}**
is less than key ***k*_{2}**. For a decision tree for insertion
sort on 3 elements, see Figure 9.5.**

- 9.8.1 Result 1: Lower Bound on Worst Case Complexity
- 9.8.2 Result 2: Lower Bound on Average Case Complexity