I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using comparison based algorithem) in just 6 steps. Can you guys help me out with this?
-
2$\begingroup$ This is a standard proof that you can probably find in any resource that deals with computational complexity or algorithm analysis. If you've found such proofs and there's something specific that you don't understand about them, please ask a question about that point. Otherwise, please do a little research. $\endgroup$– David RicherbyJul 29, 2019 at 12:57
2 Answers
The statement is not quite rigorous. Sorting requires at least $\lg(n!)$ comparisons in the worst case. Because you can very well design an algorithm that would check that the array is already sorted and stop if true. Such an algorithm would indeed sort a sorted array in $n-1$ comparisons.
This said, you can permute an array of $n$ elements in $n!$ ways, and to "unpermute" you need to somehow identify the permutation. A comparison-based algorithm is a binary decision tree, and the depth of such a tree having $n!$ leaves must be at least $\lceil\lg n!\rceil$ (because a binary tree of depth $d$ has at most $2^d$ leaves).
There are n! ways how n items in an array can be arranged. If you have k comparisons each with two possible outcomes, then you have a total of $2^k$ possible outcomes.
Therefore, if $2^k < n!$, there are at least two different arrangements of the data where all comparisons produce the same result. Since you cannot know which arrangement of data you have, you cannot sort them both correctly.