HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements

Submitted by: @import:stackexchange-cs··
0
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?

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.