元データをソートしなくても、結果用にn個のソート済み配列(flat_setとして提案されてるやつ)を用意して
そこに追加していきゃいいのでは。既に閾値以上のがn個集まってたら以降は最小のと比較して交換