4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoffrey Irving Jun 20 '16 at 0:05
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.