The worst case complexity of any sorting algorithm that only uses key comparisons is
The average case complexity of any sorting algorithm that only uses key comparisons is
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
Basically, y represents a state consisting of the information
x plus the fact that the key k1
is less than key k2. For a decision tree for insertion
sort on 3 elements, see Figure 9.5.