This question already has an answer here:

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, Gaste Apr 27 '15 at 9:53

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ 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. $\endgroup$ – David Richerby Apr 21 '15 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. Apr 22 '15 at 0:39
  • 1
    $\begingroup$ See also cs.stackexchange.com/q/6562/755 (possible dup?) $\endgroup$ – 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.

If you're not happy with this argument, the web has many, many different versions of the same proof, which you can find using your web searching skills.


Not the answer you're looking for? Browse other questions tagged or ask your own question.