# Optimal randomized comparison sorting

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?

• There is a randomized algorithm with $\mathrm{lg}(n!)+o(n)$ expected number of comparisons; see my answer here – Dmytro Taranovsky Sep 4 '18 at 17:56

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).
• 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 Sep 5 '18 at 19:26