# Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

I stumbled upon this problem on a list of open problems in the analysis of algorithms dating back to 1997. Is it still open? Can anyone point to a reference with a full or partial solution, or at least discussion?

Problem description (see link for more context):

Let $C_n$ be the number of comparisons made by quicksort to sort a random permutation of $\{1,\ldots,n\}$, when using the median of a sample of size $2t+1$ to perform the partitions and the recursive calls stop at subfiles of size $M\ge 2t+1$. Both $M$ are $t$ are constants. Compute the expected value of $C_n$ [as a function of] $M$ and $t$.

• How many comparisons does it take to compute the median? I'm pretty sure that's also open, and would be necessary to get the linear term. – Geoffrey Irving Jun 20 '16 at 0:05

## 1 Answer

I got a reply from the problem author, wanted to post the info here for reference:

Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in Transitional behaviors of the average cost of quicksort with median-of-(2t+1).

I also found that googling quicksort "2t+1" yields the above paper :).