>>136
5で割り切れないときとかを端折って証明も添えたけど
理解できないか？

その辺の教科書によく書いてある有名な話だよ。

実際は、重いピボット選択を適当にサボるほうが平均的には速い。

gcc の nth_element の実装はサボってる。
(だから平均 O(n), 最悪 O(nlogn))