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?
Optimal randomized comparison sorting
ds.algorithms;reference request;sorting