The Pivot from Group Medians

The key idea: draw the groups as columns

Sort each group and stand it up as a column, smallest at the top. Order the columns by their medians. The pivot is the median of the middle column. Everything above and to the left of the pivot is smaller than it: each column to the left has a median below the pivot, and that median's upper part is smaller still. Nothing else is forced. An input can put every other element above the pivot.

So the fewest elements smaller than the pivot is exactly the forced block. There are $\lceil q/2\rceil -1$ columns to the left, each with $\lceil g/2\rceil$ elements up to and including its median, plus the $\lceil g/2\rceil -1$ elements above the pivot in its own column. That gives $\lceil q/2\rceil \lceil g/2\rceil -1$ in total.

• Part A, $g=3$, $n=27$: $5·2-1=9$, so 17 larger elements survive when the answer lies above the pivot.
• Part B, $g=5$, $n=125$: $13·3-1=38$.
• Part D: build exactly that picture. Give the left columns small values up to their medians, the pivot's column small values above the pivot, the pivot a middle value, and everything else large values.

Part C: the fractions that must add up to less than one

The two recursive calls get about $n/g$ elements and at most $n$ minus the guaranteed discard. On the small side the pivot guarantees about $\frac{n}{2g}\lceil g/2\rceil$ elements. On the large side it guarantees about $\frac{n}{2g}(g-\lceil g/2\rceil +1)$. The worst case keeps $1-\frac{1}{2g}min(\lceil g/2\rceil ,g-\lceil g/2\rceil +1)$ of the input. The recurrence $T(n)\le T(n/g)+T(\text{kept})+O(n)$ is linear exactly when the two fractions add up to less than 1.

So $g=5,6,7,8,9$. Five is the smallest that works, which is why the textbooks use it. Six works too once you take the lower median, with a weaker bound than 5 (11/12 against 9/10). At $g=3$ and $g=4$ the fractions add up to exactly 1, so every level of the recursion does linear work and the analysis only gives $O(n\log n)$. That is a statement about this recurrence: it does not prove linear time for groups of 3 or 4. It does not say that no method built on groups of 3 is linear, and one is (see Chen and Dumitrescu below).

Why no test told you this

Measured on random, sorted, reversed and many-duplicates inputs from 250 to 4,000 elements, groups of 3 and groups of 5 both stay between 9 and 12 comparisons per element, while sorting climbs from under 10 to over 15. The extra $\log n$ factor of groups of 3 grows too slowly to show at sizes anyone tests. The difference is real, and only the argument shows it. That is the point of the recurrence.

Going further

• Groups of 3 or 4 can be rescued. Chen and Dumitrescu repeat the grouping step: take medians of groups of 3, then medians of groups of 3 of those, before recursing. The guaranteed discard becomes large enough to make the sum drop below 1.
• The constant. Blum, Floyd, Pratt, Rivest and Tarjan's original analysis gives at most about $5.43n$ comparisons with a more careful algorithm. The best known lower bound for finding the median is about $(2+ϵ)n$ (Dor and Zwick).
• In practice libraries use introselect: quickselect with median-of-3 pivots, falling back to a guaranteed-linear method only if the recursion goes too deep.

References

1. M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences 7(4), 1973.
2. K. Chen, A. Dumitrescu. Select with groups of 3 or 4. Algorithms and Data Structures (WADS), 2015.
3. D. Dor, U. Zwick. Median selection requires $(2+ϵ)n$ comparisons. SIAM Journal on Discrete Mathematics 14(3), 2001.