配列の長さが n で、1 <= m <= n^0.5 の場合
選択アルゴリズムを使用して、m 番目に小さい整数 ( http://en.wikipedia.org/wiki/Selection_algorithmに O(n) であるBFPRT と呼ばれる複雑なものがあります) を見つけて、それをピボットとして使用できると思います。配列を分割して、最初の m 個の最小整数を取得します。
しかし、最小ヒープなどのデータ構造を使用してこれを行う方法はありますか? そして、それがO(n)かどうかをどうやって知ることができますか?