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