snippetMinor
A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements
Viewed 0 times
necessarythenumberconditionelementsforandsortrequiredsufficient
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#92729, answer score: 4
Revisions (0)
No revisions yet.