Median of Mediansを書いた
長さ$ Nの配列から$ O(N)で$ k番目の要素を求める有名アルゴリズム「Median of Medians」を使ったクイックセレクトを書いてみました。
実装
（読め！すべての説明をそこに書いてきた）
えらいところ:
Cloneを要求していない
空間計算量が$ O(\log N)
えらくないところ:
参照の深さが$ O(\log N)（ど🐮てこんなことに……）
与えられた配列を破壊的に変更する
k番目の値以外は位置が保証されない
これを使って最悪$ O(N \log N)のクイックソートを書いてみた