-1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by David Richerby, Apass.Jack, xskxzr, Evil, Gilles Jul 29 at 15:59

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.

  • 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 Richerby Jul 29 at 12:57
0
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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