ソート
配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。 計算時間の表記に用いている記号 O(オー)については、ランダウの記号を参照。
以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。
次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2 を仮定している(<< は「十分小さい」)。
次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。
インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート(tag sort)」などと呼ぶこともある。
別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。
これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。
二分決定木の高さを m {\displaystyle m} とした時、木の形によらず、葉の数は 2 m {\displaystyle 2^{m}} 以下になる。 n {\displaystyle n} 要素からなるリストの(添字の)置換は n ! {\displaystyle n!} 個存在するが、任意の入力に対してアルゴリズムが正しい出力をするためには、 n ! {\displaystyle n!} 個の異なるリストを入力した際、それらがすべて異なる葉に到達できるようにしなければならない。よって、葉の数は n ! {\displaystyle n!} 以上でなければならない。以上より、 n ! ≤ 2 m {\displaystyle n!\leq 2^{m}} である。スターリングの公式より ( n e ) n < n ! {\displaystyle \left({\frac {n}{e}}\right)^{n}<n!} なので、 ( n e ) n < 2 m {\displaystyle \left({\frac {n}{e}}\right)^{n}<2^{m}} 。