<p>You can use blocks of size 3! Yes, I'm as surprised as you are. In 2014 (you asked in 2010) there came a paper which shows how to do so.</p>

<p>The idea is as follows: instead of doing <code>median3</code>, <code>partition</code>, <code>median3</code>, <code>partition</code>, ..., you do <code>median3</code>, <code>median3</code>, <code>partition</code>, <code>median3</code>, <code>median3</code>, <code>partition</code>, ... . In the paper this is called "The Repeated Step Algorithm".</p>

<p>So instead of:</p>

<pre><code>T(n) &lt;= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)
</code></pre>

<p>one gets:</p>

<pre><code>T(n) &lt;= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)
</code></pre>

<p>The said article is <a href="http://arxiv.org/abs/1409.3600" rel="noreferrer">Select with Groups of 3 or 4 Takes Linear Time</a> by K. Chen and A. Dumitrescu (2014, arxiv), or <a href="http://www.cs.uwm.edu/faculty/ad/select.pdf" rel="noreferrer">Select with groups of 3 or 4</a> (2015, author's homepage).</p>

<p>PS: The <a href="https://arxiv.org/abs/1606.00484" rel="noreferrer">Fast Deterministic Selection</a> by A. Alexandrescu (of D language fame!) which shows how to implement the above even more efficiently.</p>
Optimal median of medians selection - 3 element blocks vs 5 element blocks?
<p>I'm working on a quicksort-variant implementation based on <a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm" rel="noreferrer">the Select algorithm</a> for choosing a good pivot element. Conventional wisdom seems to be to divide the array into 5-element blocks, take the median of each, and then recursively apply the same blocking approach to the resulting medians to get a "median of medians".</p>

<p>What's confusing me is the choice of 5-element blocks rather than 3-element blocks. With 5-element blocks, it seems to me that you perform <code>n/4 = n/5 + n/25 + n/125 + n/625 + ...</code> median-of-5 operations, whereas with 3-element blocks, you perform <code>n/2 = n/3 + n/9 + n/27 + n/81 + ...</code> median-of-3 operations. Being that each median-of-5 is 6 comparisons, and each median-of-3 is 2 comparisons, that results in <code>3*n/2</code> comparisons using median-of-5 and <code>n</code> comparisons using median-of-3.</p>

<p>Can anyone explain this discrepancy, and what the motivation for using 5-element blocks could be? I'm not familiar with usual practices for applying these algorithms, so maybe there's some way you can cut out some steps and still get "close enough" to the median to ensure a good pivot, and that approach works better with 5-element blocks?</p>