# 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?

• This is a standard proof that appears in any book about algorithms. See, for example, Wikipedia's page on comparison sorts. If there's something specific you don't understand about the proof, please edit your question to address that. – David Richerby Apr 21 '15 at 19:54
• What have you tried? Where did you get stuck? We do not want to just do your exercise problem for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. Also, we expect you to do a significant amount of research before asking, including consulting standard textbooks and Wikipedia. If you haven't checked them, you probably haven't done enough research. – D.W. Apr 22 '15 at 0:39
• See also cs.stackexchange.com/q/6562/755 (possible dup?) – D.W. Apr 22 '15 at 0:42

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.