partial_sortなんてあったのか……orz
でもquickselectは元データを並び替えてしまうから
それができないならこのスレに書かれた方法でもいいけどな(負け惜しみ)

負け惜しみついでに>>290の議論だが、mは元データの個数、nは欲しい個数として
>>282の閾値以上を抽出してから一括してソートは
最速のソートが使えるのでオーダーはO(m log m)、空間使用量は元データと同じ作業領域がいるのでmに比例
>>288(俺)のソート済み配列に追加していくのは
挿入ソートを小分けにしてるわけだからオーダーはO(m*n)、空間使用量はnに比例

nとmが近いかそもそものデータ量が小さければ>>282が、そうでなければ>>288有利かな
……で良いと思う