Based on QuickSelect, let$$s define a new algorithm DeterministicSelect that deter$-$

ministically picks a consistently good pivot every time. This pivot$-$selection strategy is called

$$Median of Medians$,$ so that the worst$-$case runtime of DeterministicSelect$($A$,$ k$)$ is

O$($n$).$

Median of Medians

$1.$ Group the array into $$n$/5$ groups of $5$ elements each $($ignore any

leftover elements$)$

$2.$ Find the median of each group of $5$ elements $($as each group has a

constant $5$ elements, finding each individual median is O$(1))$

$3.$ Create a new array with only the $$n$/5$ medians, and find the true

median of this array using DeterministicSelect.

$4.$ Return this median as the chosen pivot

$($b$)$ Let p be the pivot chosen by DeterministicSelect on A$.$ Show that at least $3$n$/10$

elements in A are less than or equal to p$,$ and that at least $3$n$/10$ elements are greater

than or equal p$.$