1つのことを行う上で、いくつもアルゴリズムがあるということはよくあります。それでは、どのような基準で比較すればいいのでしょうか。
各種のソートアルゴリズム
ここでなぜソートを例にしたかというと、
- アルゴリズムが多数存在する
- そして、よく知られている
- 比較した時の差もわかりやすい
などの事情があります。なお、各ソート手法については、別途で調べてください（投げやり）。
速度の評価
アルゴリズムの速度は、よく、$O(f(n))$のような記法で表されます。これは、「$n\to\infty$となる場合に」処理時間はどう変化するか、というものです。つまり、nが充分大きな場合についての考察です。ものによっては、「充分大きな」$n$が、現実的な規模の問題では考慮しなくていいほど果てしなく大きい、ということもあります。また、ソートについても、個数が10個ぐらいのごく小規模な場合、クイックソートより挿入ソートのほうが速く終わることも多いです。
以下に、どのような規模のアルゴリズムがあるか、例を挙げてみます。
- $O(1)$…規模にかかわらず同じ時間（定数時間）。たとえば、配列から1つの値を選ぶ、ような操作が該当します。
- $O(\log n)$…規模の対数に比例するもの。例えば、ユークリッドの互除法による最大公約数の計算があります。
- $O(n)$…規模に比例するもの。例えば、「バラバラに並んだ配列から最大値を探す」ような場合が該当します。
- $O(n \log n)$…クイックソートなどがこのあたりです。
- $O(n^2)$…選択ソート・挿入ソート・バブルソートなど、シンプルなソート法はこのあたりに相当します。
- $O(n!)$、$O(2^n)$…こういった、多項式ですらない時間がかかるようになると、問題の規模が大きくなれば「実質解けない」ことになってしまいます。
最速の場合・最遅の場合
マージソートやヒープソート・選択ソートなど、どんな配列を入れても同等の時間でソートされるアルゴリズムもありますが、挿入ソートは最初からソートされた配列なら$O(n)$で終わってしまいますし、逆にクイックソートに妙な配置にした配列を投入すると$O(n^2)$かかってしまうこともありえます。
消費メモリ量（内部ソート・外部ソート）
挿入ソートは元の配列以外には、配列の長さにかかわらず一時的に配列から外した要素の分のメモリ（$O(1)$）しか消費しません。このようなソート法を、内部ソートといいます。クイックソートの場合、スタックとして$O(\log n)$だけの領域が必要となりますが、これも内部ソートに分類することが多いです。
一方、ナイーブに実装したマージソートは$O(n)$だけのメモリを必要としますが、そのようなソートを外部ソートといいます。
また、回路として実装するようなソーティングネットワークや、並列処理を前提としたバイトニックソートのように、事前に対応したシステムの必要なアルゴリズムもあります。
速度以外の面について
以上に述べた速度やメモリ消費以外にも、アルゴリズムにはそれぞれに属性があります。
安定性
単純な数字や文字列だけのソートでは関係ないのですが、Excelのシートを並べ替えるような場合を考えると、並べ替えに使うキーが全く同じものについて、並べ替えた後にどうなるかという問題があります。挿入ソートやマージソートは、正しく実装すれば同じキーに対応したものの順序がソート後も保たれることになります（安定ソート）。一方、ヒープソートやクイックソートでは結果の順序がどうなるかは状況次第です（不安定ソート）。
なお、「元の順番」をあわせてソートすることで安定化させることも可能ですが、そうすると$O(n)$の領域を使う外部ソートとなります。
オンラインアルゴリズム
挿入ソートやマージソートのように、データが徐々に増えていくような状況でも、すでにあるデータから始めることができるアルゴリズムを、「オンラインアルゴリズム」といいます。
元データの条件
元データが「0〜9までの10通りしかない」とわかっているような場合、「0がいくつ、1がいくつ…」というように数えてから配列に詰め直す「分布数えソート」というアルゴリズムがあって、これは$O(n)$で終わります。また、桁数が決まっているようなデータであれば、この分布数えソートを桁ごとに適用する、「基数ソート」という手法もあります。
あと、bzip2の圧縮では「ブロックソート」という手法が使われていますが、同じ文字列をローテートさせたもの、ということを前提とした高効率なアルゴリズムでソートを行なっています。
巨大なデータについて
理論上は、どれだけ大きなデータでも1要素の読み書きは同じ時間、という前提になっていますが、実際のマシンで仮想記憶にデータが行くような事態になれば、この前提は成り立ちません。こういう場合は、「どれだけ同じ領域を固めてアクセスするか」のほうが問題になってきます。