ウィキペディアの表のソートについては「Help:表の作り方#再整列可能な表」を、カテゴリのソートキーについてはHelp:カテゴリ#ソートキーをご覧ください。

この項目では、整列について説明しています。16世紀スペインの神学者については「ドミンゴ・デ・ソト」をご覧ください。

ソート (英: sort) は、データの集合を一定の規則に従って並べること[1]。日本語では整列（せいれつ）、並べ替え（ならべかえ）、分類（ぶんるい）などと訳される[1]。

主に配列や連結リストのような、リストデータ構造に分類されるコレクション（コンテナ）に格納されている要素データを、全順序関係によって並べ替えることを指す。また、単に「ソート」といった場合、値の小さい方から大きい方へ順に並べる昇順（しょうじゅん、英: ascending order）を指すことが多い。その反対に値を大きい方から小さい方へ順に並べることを降順（こうじゅん、英: descending order）という。

対象となるコレクションのデータ構造や必要とされる出力、また時間的コストと空間的コストの兼ね合いによって、ソートに使われるアルゴリズムは異なる。
概要

効率的なソートは、ソート済みのデータを必要とする他のアルゴリズム（探索やマージ）の最適化にとっても重要である。また、ソートされたデータの方が人間にとっても読みやすい。形式的には、その出力は以下の2つの条件を満たさなければならない。
設定された順序（昇順または降順）に対して、逆になるような順序の出力があってはならない。

出力は入力の並べ替えでなければならない。

情報工学や計算機科学の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えばバブルソートについては、早くも1956年には解析が行われている[2]。しかし、21世紀初にも新たなソートアルゴリズムが発明されている（例えば、Timsort（英語版）は2002年に、図書館ソートは2004年に発表された）。すでに考案されているソートにも様々なアルゴリズムがあり、またアルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、分割統治法、データ構造、乱択アルゴリズム、計算量解析、O記法、時間と空間のトレードオフ、下限などが含まれる。

グラフィカルユーザインタフェース (GUI) においてよく使われるウィジェットのひとつとしてリストビュー (list view) が挙げられるが、各レコードのフィールドを表す任意のカラムについてリスト中のアイテムを昇順／降順ソートできるようになっていることが多い。
分類

計算機科学では、ソートアルゴリズムを次のように分類する。
安定ソート詳細は「安定ソート」を参照

同じ値に関して、ソート前の順序がソート後も維持されているソートを安定ソートという。

安定ソートでないソートであっても、ソート条件に元の順序を含めることで必ず安定ソートにすることが可能である。しかしながら、別途元の順序を記憶する領域が必要になることから、内部ソートであっても外部ソートになってしまう。（→#内部ソートと外部ソート）
内部ソートと外部ソート

ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソートを内部ソートという。クイックソートのような再帰を利用するアルゴリズムは、再帰のために O(log n) の領域を必要とすることからIn-placeであるか否かは議論が分かれるところであるが、これも内部ソートに含めるのが一般的である。このことから内部ソートは、ソートされるデータの格納域以外には O(1) か O(log n) の領域しか必要としない。

逆に、ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソートを外部ソートという。

メモリ使用量（およびその他の計算資源の使用量）による分類である。すべての内部ソートは、インデックスや参照、複製を作成して処理することで事実上の外部ソートにすることができる。アルゴリズムとしての本質ではないので一般的には無視されるが、高速化や柔軟な処理のために冗長な記憶領域を使用する場合がある。例えば、非安定ソートアルゴリズムで安定ソートを実現する場合など。（→#安定ソート）
比較ソート詳細は「比較ソート」を参照

個々の項目を比較演算で大小判定することを基本とするソートを比較ソートという。

比較ソートには#比較ソートの理論限界が存在する。
計算量

入力されるリストの項目数 n に基づいた計算量による分類。典型的なソートアルゴリズムでは、最善で O(n log n) 、最悪で O(n2) である。理想は O(n) である。

比較ソートでは、一般的な（ランダムに並んだ）データの並べ替えに対しては少なくとも O(n log n) の比較回数が必要である。（→#比較ソートの理論限界）
手法

汎用手法による分類。挿入、交換、選択、マージなどがある。交換ソートにはバブルソートやシェーカーソートやコムソートなどが含まれる。選択ソートにはヒープソートなどが含まれる。
再帰

再帰が必須、不可能、どちらでも可能、という分類。実装上の都合で再帰に関わる制限がある場合に注目される。
一覧

配列に格納されたn個のデータをソートする場合について、各アルゴリズムの性能を示す。計算時間の表記に用いている記号 O（オー）については、ランダウの記号を参照。

以下の表で、n はソートすべきデータ要素数である。平均実行時間と最悪実行時間は時間計算量を示している。このとき、ソートキーの長さは一定と仮定しており、比較や交換といった操作は定数時間で行われるとする。メモリ使用量は、入力データの格納域以外に必要となる領域を示している。これらは、いずれも比較ソートである。

名称
平均計算時間
最悪計算時間
メモリ使用量
安定性
手法
備考

バブルソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ○交換
シェーカーソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ○交換
コムソート n log ⁡ n {\displaystyle n\log n} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ×交換コードサイズが小さくて済む。
ノームソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ○交換
センタク/選択ソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ×選択安定ソートとしても実装可能
ソウニユウ/挿入ソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ○挿入最良計算時間が Θ ( n ) {\displaystyle \Theta (n)} になる。
シェルソート n log ⁡ n {\displaystyle n\log n} ≧ n 1.5 {\displaystyle n^{1.5}} 1 {\displaystyle 1} ×挿入最悪 Ω ( n 3 2 ) {\displaystyle \Omega (n^{\frac {3}{2}})} や Ω ( n 4 3 ) {\displaystyle \Omega (n^{\frac {4}{3}})} の数列が実用化されている。
2分木ソート n log ⁡ n {\displaystyle n\log n} n log ⁡ n {\displaystyle n\log n} n {\displaystyle n} ○挿入平衡2分探索木を使った場合
図書館ソート n log ⁡ n {\displaystyle n\log n} n 2 {\displaystyle n^{2}} n {\displaystyle n} ○挿入
マージソート n log ⁡ n {\displaystyle n\log n} n log ⁡ n {\displaystyle n\log n} n {\displaystyle n} ○マージ連結リストの場合は O ( 1 ) {\displaystyle O(1)} 外部メモリ。
In-place マージソート n log 2 ⁡ n {\displaystyle n\log ^{2}n} n log 2 ⁡ n {\displaystyle n\log ^{2}n} 1 {\displaystyle 1} ○マージ ⇒実装例
ヒープソート n log ⁡ n {\displaystyle n\log n} n log ⁡ n {\displaystyle n\log n} 1 {\displaystyle 1} ×選択
スムースソート— n log ⁡ n {\displaystyle n\log n} 1 {\displaystyle 1} ×選択
クイックソート n log ⁡ n {\displaystyle n\log n} n 2 {\displaystyle n^{2}} log ⁡ n {\displaystyle \log n} ×パーティショニングメモリはコールスタック（素朴な実装では Ω ( n ) {\displaystyle \Omega (n)} になる）
イントロソート n log ⁡ n {\displaystyle n\log n} n log ⁡ n {\displaystyle n\log n} log ⁡ n {\displaystyle \log n} ×混成メモリはコールスタック
ペイシェンスソート— n 2 {\displaystyle n^{2}} n {\displaystyle n} ×挿入 O ( n log ⁡ n ) {\displaystyle O(n\log n)} 以内にすべての最長増加部分列を探す。
ストランドソート n log ⁡ n {\displaystyle n\log n} n 2 {\displaystyle n^{2}} n {\displaystyle n} ○選択
キクウテンチ/奇偶転置ソート n 2 {\displaystyle n^{2}} n 2 {\displaystyle n^{2}} 1 {\displaystyle 1} ○交換
シェアソート n 1.5 {\displaystyle n^{1.5}} n 1.5 {\displaystyle n^{1.5}} 1 {\displaystyle 1} ×交換

次の表は、比較ソート以外のソートアルゴリズムの一覧である。そのため、下限が O(n log n) で制限されない。k はキーの長さ、s は実装で使われるチャンクのサイズである。これらの一部は、キーが十分に長く、各要素のキーが重複しないことを前提としている。すなわち、n << 2k を仮定している（<< は「十分小さい」）。

名称
平均計算時間
最悪計算時間
メモリ使用量
安定性
n << 2k?
備考

ハトノス/鳩の巣ソート n + 2 k {\displaystyle n+2^{k}} n + 2 k {\displaystyle n+2^{k}} 2 k {\displaystyle 2^{k}} ○○
バケットソート n + k {\displaystyle n+k} n 2 {\displaystyle n^{2}} n k {\displaystyle nk} ○×入力データは定義域に一様分布すると仮定
フンフカソエ/分布数えソート n + 2 k {\displaystyle n+2^{k}} n + 2 k {\displaystyle n+2^{k}} n + 2 k {\displaystyle n+2^{k}} ○○
LSD 基数ソート n k / s {\displaystyle nk/s} n k / s {\displaystyle nk/s} n {\displaystyle n} ○×
MSD 基数ソート n k / s {\displaystyle nk/s} n ( k / s ) 2 s {\displaystyle n(k/s)2^{s}} ( k / s ) 2 s {\displaystyle (k/s)2^{s}} ××
スプレッドソート n k / log ⁡ n {\displaystyle nk/\log n} n ( k − log ⁡ n ) 0.5 {\displaystyle n(k-\log n)^{0.5}} n {\displaystyle n} ××n << 2k の場合の計算時間だが、それ以外の場合でもソート可能
キヤクシヤソウ/逆写像ソート n {\displaystyle n}  ?N/A n {\displaystyle n}  ?○×

次の表は、あまりにも性能が悪いので通常は用いられないソートアルゴリズム、および特別なハードウェアが必要なソートアルゴリズムの一覧である。

名称
平均計算時間
最悪計算時間
メモリ使用量
安定性
大小比較
備考

ボゴソート n ⋅ n ! {\displaystyle n\cdot n!} ∞ 1 {\displaystyle 1} ×○平均時間はクヌースのシャッフルを使った場合
ボゾソート n ⋅ n ! {\displaystyle n\cdot n!} ∞ 1 {\displaystyle 1} ×○平均時間はボゴソートの約半分に漸近する。
ストゥージソート n 2.71 {\displaystyle n^{2.71}} n 2.71 {\displaystyle n^{2.71}} log ⁡ n {\displaystyle \log n} ×○
スリープソート値の最大値×プロセス起動単位時間（実際には誤差あり）同左 n {\displaystyle n} ?×?条件が特殊。実用の正確性が保証されない。
ビードソートN/AN/A—N/A×専用ハードウェアが必要
タンシユンハンケエキ/単純パンケーキソート n {\displaystyle n} n {\displaystyle n} log ⁡ n {\displaystyle \log n} ×○反転を定数時間で行えるものと仮定