<p>Since your question is: "What is known?" Here's something:</p>

<p><a href="http://arxiv.org/abs/1307.3033" rel="nofollow">http://arxiv.org/abs/1307.3033</a></p>

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

CC BY-SA 4.0
2018-09-05T19:26:54.203Z
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?
David Eppstein
CC BY-SA 4.0
2018-09-07T13:51:24.650Z
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, https://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?
Pat Morin
CC BY-SA 4.0
2018-09-09T00:14:25.737Z
There are definitely fluctuations but I thought (4/3)2^k was the worst case and it was better for other cases.
David Eppstein
CC BY-SA 3.0
2014-10-11T04:16:38.000Z
2014-10-11T04:16:38.000Z
Pat Morin
<p>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.</p>

<p>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.</p>

<p>What if anything is known about upper bounds for this problem? For all $n&gt;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?</p>

CC BY-SA 4.0
2018-09-04T17:56:39.850Z
There is a randomized algorithm with $\mathrm{lg}(n!)+o(n)$ expected number of comparisons; see my answer [here](https://cstheory.stackexchange.com/questions/41493/sorting-with-an-average-of-mathrmlgnon-comparisons)
Dmytro Taranovsky
<ds.algorithms><reference-request><sorting>
Optimal randomized comparison sorting
David Eppstein
# Optimal randomized comparison sorting

(Asked by: username_0 on 2014-10-10)

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?

**Tags:** ds.algorithms, reference-request, sorting

> **Comments:**
> **username_1**: There is a randomized algorithm with $\mathrm{lg}(n!)+o(n)$ expected number of comparisons; see my answer [here](https://cstheory.stackexchange.com/questions/41493/sorting-with-an-average-of-mathrmlgnon-comparisons)  

---

## 1 answers

### Answer by username_2 on 2014-10-11. Score: 4

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

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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, https://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?  
> **username_0**: There are definitely fluctuations but I thought (4/3)2^k was the worst case and it was better for other cases.  

---

