>>288
なるほど。
今全部分かった。

うーん。
それは任意の個数nと閾値以上の個数が近くないと、n個目以降が見つかる度に比較、探索、挿入を繰り返す事に。。。
データによりけりではあるけど、微妙。

>>282 は、イメージとしてはクイックソートの最初のピボットを閾値にして、閾値以下はソートしない様に変形させた感じ。

どっちがどうとかは、実測しないとなんとも言えなさそう。