部分ソート(0)

　長さがnであるような配列があったとしよう。そこから、上位m個の要素を取ってくる、という問題を考えたい。言い替えると、配列の中で上位のm個だけはソートされていることを保証してほしい、ということになる。（残りの要素はソートされていようがいまいが関係ない。）
　nが大きくないのであれば、全体をソートしても大きな問題ではない。平均するとn log nの手間でソートは出来る。ただ、これは明らかに無駄であるので、できればこの無駄を減らしたい。
　このように、「上位m個の要素だけはソートしておいてほしい」という問題設定を部分ソートという。部分ソートに関する日本語の資料がwebで見当たらなかったので、ちょっと書いてみることにした。