ソート () は、データの集合を一定の規則に従って並べること。日本語では整列（せいれつ）と訳される。（以前はその原義から分類という訳語が充てられていたが、もう使われていない）主にコンピュータソフトにおけるリストに表示するデータに対し、全順序関係によって一列に並べることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、）という。対象となるデータのデータ構造や必要な出力によって、使われるアルゴリズムは異なる。効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている。多くの人は既に解決済みの問題と考えているが、現在も新たなソートアルゴリズムが発明されている（例えば、図書館ソートが最初に発表されたのは2004年である）。様々なアルゴリズムがあり、アルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。計算機科学では、ソートアルゴリズムを次のように分類する。同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソートを内部ソートという。クイックソートのような再帰を利用するアルゴリズムは、再帰のために O(log "n") の領域を必要とすることからIn-placeであるか否かは議論が分かれるところであるが、これも内部ソートに含めるのが一般的である。このことから内部ソートは、ソートされるデータの格納域以外には O(1) か O(log "n") の領域しか必要としない。逆に、ソートされるデータの格納領域以外に O("n") 以上の一時的な記憶領域が必要であるソートを外部ソートという。メモリ使用量（およびその他の計算資源の使用量）による分類である。すべての内部ソートは、インデックスや参照、複製を作成して処理することで事実上の外部ソートにすることができる。アルゴリズムとしての本質ではないので一般的には無視されるが、高速化や柔軟な処理のために冗長な記憶領域を使用する場合がある。例えば、非安定ソートアルゴリズムで安定ソートを実現する場合など。（→#安定ソート）個々の項目を比較演算で大小判定することを基本とするソートを比較ソートという。比較ソートには#比較ソートの理論限界が存在する。入力されるリストの項目数 "n" に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O("n" log "n") 、最悪で O("n") である。理想は O("n") である。比較ソートでは、必ず O("n" log "n") の比較が必要となる。（→#比較ソートの理論限界）汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。配列に格納された"n"個のデータをソートする場合について、各アルゴリズムの性能を示す。計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。以下の表で、"n" はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O("n" log "n") で制限されない。"k" はキーの長さ、"s" は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、"n" « 2 を仮定している（« は「十分小さい」）。次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。計算理論において、"n"個のデータのソートは、データの大小比較のみによって行う場合、最悪計算量が最低でも O("n" log "n") 必要なことが知られている。O("n") で実現しているアルゴリズムは、データに対して何らかの仮定があることに注意を要する。最悪計算量が最低でもO("n" log "n") 必要である略証を示す。ソーティングはデータの並べ替えである。"n"個のデータの並べ替えは置換を用いて書け、置換は"n"!個ある。スターリングの公式より、"n"!= O("n") 。プログラム中の分岐はif文でしか起こらない。1回のif文でプログラム中は2つに分岐するので、"n"!個の置換をすべて実現する必要なif分岐の個数を"m"とすると、2 ≧ "n"!= O("n") でなければならない。したがって、ソーティングの最悪計算量は最低でも "m" = O("n" log "n") である。ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な補助記憶装置が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域のスワップ回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。例えば、再帰型のクイックソートは主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。対策の一つとして、ソート対象の配列の要素が（関係データベースのような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある。別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果をマージソートでマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて仮想記憶の性質に合うよう設計する必要がある。

出典:wikipedia