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

<p>Apparently the problem was solved by Pascal Hennequin in his PhD thesis. Chern and Hwang discuss the solution in <a href="http://algo.stat.sinica.edu.tw/hk/?p=51" rel="nofollow">Transitional behaviors of the average cost of quicksort with median-of-(2t+1)</a>.</p>

<p>I also found that googling <code>quicksort "2t+1"</code> yields the above paper :).</p>

CC BY-SA 3.0
2016-06-20T20:25:07.843Z
2016-06-20T21:56:23.763Z
2016-06-20T21:56:23.763Z
Elliot Gorokhovsky
<p>I stumbled upon <a href="http://algo.inria.fr/AofA/Problems/src/Q2.stat.txt">this problem</a> on a <a href="http://algo.inria.fr/AofA/Problems/">list</a> 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?</p>

<p>Problem description (see link for more context):</p>

<blockquote>
  <p>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$.</p>
</blockquote>

CC BY-SA 3.0
2016-06-20T00:05:34.783Z
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
<sorting>
Quicksort: compute the expected number of comparisons as a function of $M$ and $t$
Elliot Gorokhovsky
# Quicksort: compute the expected number of comparisons as a function of $M$ and $t$

(Asked by: username_0 on 2016-06-19)

I stumbled upon [this problem](http://algo.inria.fr/AofA/Problems/src/Q2.stat.txt) on a [list](http://algo.inria.fr/AofA/Problems/) 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$.

**Tags:** sorting

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2016-06-20. Score: 3 | Accepted 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)](http://algo.stat.sinica.edu.tw/hk/?p=51).

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


---

