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

Improve this question
$\endgroup$
1
  • 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
    Commented Jun 20, 2016 at 0:05

1 Answer 1

Reset to default
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 :).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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