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

$($a$)$ Show that the worst$-$case runtime of DeterministicSelect$($A$,$ k$)$ using the $$Median

of Medians$$ strategy is O$($n$).$