4
$\begingroup$

I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision tree for any comparison based sorting algorithms must have at least $n!$ leaves, and therefore at least one path of length $\left\lceil \log_{2}\left(n!\right)\right\rceil $, corresponding to the worst case performance of said algorithm.

Question: The condition $$\left\lceil \log_{2}\left(n!\right)\right\rceil \leq\#\text{ of comparisons in the worst case}$$

is a necessary condition for any comparison based sorting algorithm. Is it also sufficient? e.g. if I am asked if it is possible to sort 5 elements in 7 comparisons, does it suffice to observe that $\log_{2}\left(5!\right)<7$ to deduce that such an algorithm must exist?

$\endgroup$
  • 1
    $\begingroup$ Possibly useful: cs.stackexchange.com/q/43493/755 $\endgroup$ – D.W. Jun 4 '18 at 20:29
  • $\begingroup$ It's not sufficient. The exact minimal number of comparisons needed is unknown in general, but it deviates from this simple lower bound, I believe. $\endgroup$ – Yuval Filmus Jun 4 '18 at 21:18
4
$\begingroup$

Following the conventions of Peczarski, Towards Optimal Sorting of 16 Elements, let us denote by $S(n)$ the optimal number of comparisons needed, and by $C(n)$ the information-theoretic lower bound $\lceil \log_2 n! \rceil$. It is known that $S(n) = C(n)$ for all $n \leq 11$, but $S(n) = C(n)+1$ for $12 \leq n \leq 15$. See Peczarski's paper for references. See also A036604.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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