選択アルゴリズム
このアルゴリズムにかかる時間は O(n + klogk) であり、実際非常に効率が良い。特に、n に比較して k が十分小さいなら、選択ソートを使うようにすれば効率が向上する。
選択する k 個の要素がソートされている必要がないなら、もっと効率化することができる。その場合、k 番目の要素を含むパーティションだけに再帰を施せばよく、その前後はソートする必要がない。
このアルゴリズムに掛かる時間は O(n) であり、アルゴリズムとしては最善の部類になる。
別の方法はトーナメントアルゴリズムである。まず、隣接するペアで試合(比較)を行い、勝者を次の試合に進めていき、最終的に優勝を決定する。このときトーナメント木を生成する。この時点で 2位の要素は優勝者に直接負けた要素であるはずなので、木構造を辿っていけば O(log n) の時間で探すことができる。このとき新たなトーナメント木を生成する。3位の要素は 2位の要素に直接負けた要素のはずなので、2つのトーナメント木からそれを探し出す。このようにして k 個の要素を探し出すまで処理を行う。このアルゴリズムは O(n + k log n) の時間がかかる。
k = 2 の場合、O(n + log n) の時間で選択ができる。