# Worst case of based on comparison sorting algorithm [duplicate]

Explain by reference to the structure of a decision tree why any sorting algorithm based on comparisons cannot in its worst case use fewer comparison than a number proportional to nlog(n).

Any ideas how I can prove this?

## marked as duplicate by D.W.♦, David Richerby, Juho, Rick Decker, GasteApr 27 '15 at 9:53

This is very, very classical. Here is the idea. You can describe a run of your algorithm as a decision tree. At each node there is a comparison operation performed by your algorithm, and the three children correspond to the three different answers. Every execution of your algorithm ends at a leaf. Since at the end the list is sorted, in particular we can tell what the original order of the list was. So we can annotate each leaf by a permutation on $n$ elements. Since there are $n!$ different permutations, there must be at least $n!$ leaves, so the tree must have height at least $\Omega(\log_3 n!) = \Omega(n\log n)$. This means that there is some computation path that will result in $\Omega(n\log n)$ comparisons.