# Why do you need at least ln(n!) many comparison to sort a list?

"If every element comparison (testing whether $$a_i \le a_j$$ ) provides at most one bit of information, argue that you need at least on the order of $$\ln(n!)$$ many tests/comparisons to sort the list."

This is a question on my homework at the moment. I don't understand how I'm supposed to go about arguing this as I don't quite understand why it is true. Any pointers in the right direction? Thanks.

• There should be explicit pointers in your course material such as textbook or lecture note. Can you summarize what you had learned just before this homework? Nov 24, 2018 at 1:02
• This question is in reference to what was taught a few lectures back and so I can't recall it as well as I should but we proved the worst case Big Oh time-complexity of merge sort and insertion sort. Our professor talked about the minimal amount of work required to sort a list but I'm a bit lost on that part although I feel as if the answer is related to that. Nov 24, 2018 at 1:11
• @toshko3331 Search for lower bounds on sorting, you should get your answer. Nov 24, 2018 at 1:57

You should model the comparison based sorting problem with decision tree where each node represents a comparison. You should see there are $$n!$$ leaves of such tree each contributes to a possibility of sorted array. If $$h$$ is the height of such tree, then $$2^{h} \geq {n!}$$ follows.
With k decisions, you may be able to reduce the possibilities to $$n! / 2^k$$ possibilities. You need to reduce the possibilities to only one, and for that you need to make at least $$log_2 (n!)$$ decisions.
With fewer than $$log_2 (n!)$$ decisions, there must be at least two permutations where all those decisions would give the same outcome, and since you don't know which of these two permutations you started with, you can't sort both permutations correctly.