12

I'm working on a quicksort-variant implementation based on the Select algorithm 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".

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 n/4 = n/5 + n/25 + n/125 + n/625 + ... median-of-5 operations, whereas with 3-element blocks, you perform n/2 = n/3 + n/9 + n/27 + n/81 + ... median-of-3 operations. Being that each median-of-5 is 6 comparisons, and each median-of-3 is 2 comparisons, that results in 3*n/2 comparisons using median-of-5 and n comparisons using median-of-3.

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?

2
  • Any block size larger than 3 is guaranteed linear time. The even sizes might sound like a bad choice, but you choose a different rank other than the median (so whether the pivot is smaller or larger than the rank you're searching for, it worst-case discards the same size).
    – Elliott
    Sep 21, 2020 at 15:50
  • 1
    I'm interested to see genuine proofs on why blocks of size 2 and 3 aren't linear. We can deduce that T(n) = T(an) + T(bn) + O(n) is linear if a+b < 1, but I don't know how to prove the opposite.
    – Elliott
    Sep 21, 2020 at 15:50

3 Answers 3

12

The reason is that by choosing blocks of 3, we might lose the guarantee of having an O(n) time algorithm.

For blocks of 5, the time complexity is

T(n) = T(n/5) + T(7n/10) + O(n)

For blocks of 3, it comes out to be

T(n) = T(n/3) + T(2n/3) + O(n)

Check this out: http://www.cs.berkeley.edu/~luca/w4231/fall99/slides/l3.pdf

4
  • 1
    Just curious, can you clarify how from "T(n) ≤ T(n/5) + T(0.7n) + cn" follows "T(n) ≤ c*n*(1 + (9/10) + (9/10)^2 + ...)" ? That's the one part I don't get in wikipedia article and your paper. Thanks! Oct 11, 2010 at 17:23
  • @Nikita: One way to see it is to write it as T(n) <= T(7n/10) + cn + cn/5 + cn/25 + .... Then write it as T(n) <= cn + (7cn/10 + cn/5) + (49cn/100 + cn/25) + ... + <= cn + cn*9/10 + cn*(9/10)^2 + ...
    – Aryabhatta
    Oct 11, 2010 at 17:32
  • @NikitaRybak : you have to unravel the recursion. I recommend using alpha and beta instead of the actual constants. after 3 (painstaking) levels, you'll see a pattern. cn*[1 + (a+b) + (a+b)^2 + (a+b)^3 + ...]. NOW: note that this is a geometric series, and the sum converges to 1/(1-r) if r<1! Which is true in our case but NOT in the 3-element case
    – ihadanny
    Jan 1, 2016 at 10:11
  • @ihadanny, that isn't what I got. For each element a^i * b^j there's a multiplicative constant, (i+j)! / i! / j!. My overall result for the complexity is O(n * sum[i = 0 -> loga(n)] sum [j = 0 -> logb(n/a^i)] (i+j)! / i! / j! * a^i * b^j, which doesn't seem to simplify down to what you've got.
    – Elliott
    Sep 21, 2020 at 15:17
6

I believe it has to do with assuring a "good" split. Dividing into 5-element blocks assures a worst-case split of 70-30. The standard argument goes like this: of the n/5 blocks, at least half of the medians are >= the median-of-medians, hence at least half of the n/5 blocks have at least 3 elements (1/2 of 5) >= median-of-medians, and this gives a 3n/10 split, which means the other partition is 7n/10 in the worst case.

That gives T(n) = T(n/5) + T(7n/10) + O(n).

Since n/5 + 7n/10 < 1, the worst-case running time is O(n).

Choosing 3-element blocks makes it thus: at least half of the n/3 blocks have at least 2 elements >= median-of-medians, hence this gives a n/3 split, or 2n/3 in the worst case.

That gives T(n) = T(n/3) + T(2n/3) + O(n).

In this case, n/3 + 2n/3 = 1, so it reduces to O(n log n) in the worst case.

4

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.

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

So instead of:

T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)

one gets:

T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)

The said article is Select with Groups of 3 or 4 Takes Linear Time by K. Chen and A. Dumitrescu (2014, arxiv), or Select with groups of 3 or 4 (2015, author's homepage).

PS: The Fast Deterministic Selection by A. Alexandrescu (of D language fame!) which shows how to implement the above even more efficiently.

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.