Median of the median algorithm: why divide the array into blocks of size 5

Question

In the median median algorithm, we need to divide the array into pieces of size 5. I wonder how the inventors of the algorithms came up with the magic number "5", and not maybe 7, or 9, or something else?

Answer 1

I think that if you check the "Proof of O (n) running time" section of the wiki page for the median median algorithm :

The median-calculating recursive call does not exceed the worst linear behavior, because the median list is 20% of the list size, while the other recursive call recurses no more than 70% of the list, doing the work time

O (n) member cn for working with the partition (we visited each element a constant number of times to form them in n / 5 groups and take each median O (1) times). From here, using induction, it is easy to show that

This will help you understand why.

Answer 2

The number must be greater than 3 (and obviously an odd number) for the algorithm. 5 is the smallest odd number greater than 3. Thus, 5 was chosen.

Answer 3

You can also use blocks of size 3 or 4, as shown in the document Select with Groups 3 or 4 K. Chen and A. Dumitrescu (2015). The idea is to use the "median median" algorithm twice and separate only after that. This reduces the quality of the turn, but faster.

So, instead of:

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

gets:

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