中位數的中位數選擇（median of medians）

要用快速選擇（quickselect）或快速排序把陣列切得好，你會想要一個接近中間的樞紐——但不先做工就不知道中間在哪。中位數的中位數是個巧妙的自我啟動技巧，能快速產生一個可證明良好的樞紐，保證選擇問題的最壞情況線性時間。它正是把「找第 k 小的元素」從碰運氣變成有保證的演算法。

選樞紐的程序：把 n 個元素分成每五個一組；找出每組的中位數（很容易，因為五個元素以常數時間排序）；然後對那 n/5 個組中位數遞迴套用整個選擇演算法，找出它們的中位數——即「中位數的中位數」。用這個值當樞紐。神奇之處在於一個計數論證：這個樞紐保證大於至少 3/10 的元素、也小於至少 3/10，所以每次以它分割都至少丟掉約 30% 的陣列。遞迴關係式變成 T(n) = T(n/5) + T(7n/10) + O(n)：一次遞迴呼叫在五分之一的資料上選樞紐、一次在存活的至多 70% 上、加上線性的分割工作。因為 1/5 + 7/10 = 9/10 嚴格小於 1，這解得 O(n)——最壞情況線性。

中位數的中位數出自 Blum、Floyd、Pratt、Rivest 與 Tarjan（故稱 BFPRT 演算法），是一座里程碑：它證明選擇能以確定性線性時間完成，不需隨機、也沒有壞的最壞情況。但它在實務上的誠實定位多半是理論性的：那個 O(n) 隱藏的常數因子很大，所以期望 O(n) 且常數極小的隨機快速選擇，在真實輸入上幾乎總是更快。中位數的中位數在對手控制輸入、或需要有保證的界時，作為安全的樞紐規則才真正派上用場。