12
$\begingroup$

So we all know the comparison-tree lower bound of $\lceil\log_2 n!\rceil$ on the worst-case number of comparisons made by a (deterministic) comparison sorting algorithm. It does not apply to randomized comparison sorting (if we measure the expected comparisons for the worst case input). For instance, for $n=4$, the deterministic lower bound is five comparisons, but a randomized algorithm (randomly permute the input and then apply merge sort) does better, having $4\frac{2}{3}$ comparisons in expectation for all inputs.

The $\log_2 n!$ bound without the ceilings does still apply in the randomized case, by an information-theoretic argument, and it can be slightly tightened to $$k+\frac{2(n!-2^k)}{n!} \text{, where } k=\lfloor\log_2 n!\rfloor.$$ This follows because there is an optimal algorithm that randomly permutes the input and then applies a (deterministic) decision tree, and the best decision tree (if it exists) is one in which all leaves are in two consecutive levels.

What if anything is known about upper bounds for this problem? For all $n>2$, the randomized number of comparisons (in expectation, for the worst-case input, for the best possible algorithm) is always strictly better than the best deterministic algorithm (essentially, because $n!$ is never a power of two). But how much better?

Improve this question
$\endgroup$
1
  • $\begingroup$ There is a randomized algorithm with $\mathrm{lg}(n!)+o(n)$ expected number of comparisons; see my answer here $\endgroup$
    – Dmytro Taranovsky
    Commented Sep 4, 2018 at 17:56

1 Answer 1

Reset to default
4
$\begingroup$

Since your question is: "What is known?" Here's something:

http://arxiv.org/abs/1307.3033

This gives an average case analysis of the Ford-Johnson Algorithm. The expected number of comparisons is $\log n! +cn$ for a surprisingly small constant $c$ (about .05).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Pat: maybe you could explain to me why this analysis is helpful. The original analysis shows that the worst case number of comparisons is $n\log n-1.415n$. This one shows that the expected number of comparisons is $n\log n-1.399n$. Am I confused? It seems like the worst case bound is better than the expected bound. But the authors state the worst case bound and then go to some effort to prove that the average case bound has a tighter constant. Did they state something wrong? $\endgroup$
    – David Eppstein
    Commented Sep 5, 2018 at 19:26
  • $\begingroup$ I'm no expert, the only reason I know about any of this is John Iacono. I think, though, that it has to do with fluctuations based on how close n is to (4/3 times) a power of 2. If you look at the analysis on Page 71 here, link.springer.com/content/pdf/10.1007%2FBF01934989.pdf , the -1.415n bound seems to only hold when n = floor((4/3)2^k) for some integer k. Maybe the -1.329n bound in Knuth is the best that holds for all n? $\endgroup$
    – Pat Morin
    Commented Sep 7, 2018 at 13:51
  • $\begingroup$ There are definitely fluctuations but I thought (4/3)2^k was the worst case and it was better for other cases. $\endgroup$
    – David Eppstein
    Commented Sep 9, 2018 at 0:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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