http://i.imgur.com/cmfwn1S.jpg
因為在解釋裡好像沒特別說是用什麼樣的sorting方式，其他算法大多是用comparison ba
se
還有T(n)=T(n/5)+T(3n/4)+O(n)→→→這個O(n)是哪來的QQ

他又不是做sortingO(n)是1.2.4步的時間5個數排列 就算用初等排序 也才5^2=25是一個常數 然後又有n/5組 所以那一步還是花n的時間遞迴求中位數的中位數那只是把一堆中位數再丟下去遞迴 所以時間就是T(n/5)而且遞迴也不是排列中位數 而只是要找中位數的中位數 所以遞迴下去也只是要找那n/5個數中的第n/2大的數而已1.2.4各花n 加起來還是n 所以他就省略了

Sort o(n)是因為每堆只有5個 假設採n log n的sorting 也才5log5 是常數 因為有n/5堆 所以總共是nlog5 是O(n)

那個O(n)你用第四步驟看 全部的數跟P比大小分堆 至少要比較n次

可以google median of median 網路上有很多講解～