ソートのソースを表示

{{WikipediaPage|ウィキペディアの表のソートについては「[[Help:表の作り方#再整列可能な表]]」を、カテゴリのソートキーについては[[Help:カテゴリ#ソートキー]]をご覧ください。}}
{{otheruses|整列|16世紀スペインの神学者|ドミンゴ・デ・ソト}}

'''ソート''' ({{lang-en-short|sort}}) は、[[データ]]の集合を一定の規則に従って並べること<ref name="Kotobank">{{Cite web|和書|url=https://kotobank.jp/word/ソート|title=ソート|publisher=[[コトバンク]]|author=ASCII.jpデジタル用語辞典|accessdate=2020-06-01|language=ja|ref={{SfnRef|kotobank-ソート}}}}</ref>。日本語では'''整列'''（せいれつ）、'''並べ替え'''（ならべかえ）、'''分類'''（ぶんるい）などと訳される<ref name="Kotobank" />。

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

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

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

# 設定された順序（昇順または降順）に対して、逆になるような順序の出力があってはならない。
# 出力は入力の並べ替えでなければならない。

[[情報工学]]や[[計算機科学]]の黎明期から、ソートは単純な問題でありながら効率的に解くことが難しく、そのためもあって盛んに研究されてきた。例えば[[バブルソート]]については、早くも1956年には解析が行われている<ref>[http://www.cs.duke.edu/~ola/papers/bubble.pdf Bubble Sort: An Archaeological Algorithmic Analysis] Owen Astrachan</ref>。しかし、21世紀初にも新たなソートアルゴリズムが発明されている（例えば、{{仮リンク|Timsort|en|Timsort}}は2002年に、[[図書館ソート]]は2004年に発表された）。すでに考案されているソートにも様々なアルゴリズムがあり、またアルゴリズムという概念を学習するのに最適なので、情報工学や計算機科学での入門的題材として広く親しまれている。例えば、[[分割統治法]]、[[データ構造]]、[[乱択アルゴリズム]]、[[計算複雑性理論|計算量]]解析、[[ランダウの記号|O記法]]、[[時間と空間のトレードオフ]]、下限などが含まれる。

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

== 分類 ==
[[計算機科学]]では、ソートアルゴリズムを次のように分類する。

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

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

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

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

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

=== 比較ソート ===
{{main|比較ソート}}

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

比較ソートには[[ソート#比較ソートアルゴリズムの最悪計算量の下界|#比較ソートの理論限界]]が存在する。

=== 計算量 ===
入力されるリストの項目数 ''n'' に基づいた[[計算複雑性理論|計算量]]による分類。典型的なソートアルゴリズムでは、最善で [[ランダウの記号|O]](''n''&nbsp;log&nbsp;''n'') 、最悪で O(''n''<sup>2</sup>) である。理想は O(''n'') である。

比較ソートでは、一般的な（ランダムに並んだ）データの並べ替えに対しては少なくとも O(''n''&nbsp;log&nbsp;''n'') の比較回数が必要である。（→[[ソート#比較ソートアルゴリズムの最悪計算量の下界|#比較ソートの理論限界]]）

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

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

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

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

{|class="wikitable sortable" style="font-size:95%; margin-right:0px;"
|-style="line-height:1.4em; vertical-align:bottom; white-space:nowrap;"
!style="width:10.5em"|名称<br />!!style="width:14ex; white-space:nowrap;"|[[計算量|平均計算時間]]<br />!!style="width:21ex; white-space:nowrap;"|[[計算量|最悪計算時間]]<br />!!style="white-space:nowrap;"|[[メモリ]]使用量<br />!!style="width:3em"|{{Nowrap|[[安定ソート|安定性]]}}<br />!!手法<br />!!備考<br />
|-
|[[バブルソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|交換
|
|-
|[[シェーカーソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|交換
|
|-
|[[コムソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|交換
|コードサイズが小さくて済む。
|-
|[[ノームソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|交換
|
|-
|{{Display none|センタク/}}[[選択ソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|選択
|安定ソートとしても実装可能
|-
|{{Display none|ソウニユウ/}}[[挿入ソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|挿入
|最良計算時間が<math>\Theta(n)</math>になる。
|-
|[[シェルソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ffdddd"|≧<math>n^{1.5}</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|挿入
|最悪<math>\Omega(n^\frac{3}{2})</math>や<math>\Omega(n^\frac{4}{3})</math>の数列が実用化されている。
|-
|{{仮リンク|2分木ソート|en|Tree sort}}
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>n \log n</math>
|<math>n</math>
|style="background-color:#ddffdd"|○
|挿入
|[[平衡2分探索木]]を使った場合
|-
|[[図書館ソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|<math>n</math>
|style="background-color:#ddffdd"|○
|挿入
|
|-
|[[マージソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>n \log n</math>
|<math>n</math>
|style="background-color:#ddffdd"|○
|マージ
|[[連結リスト]]の場合は<math>O (1)</math>外部メモリ。
|-
| style="white-space:nowrap;" |[[In-placeアルゴリズム|In-place]] [[マージソート]]
|<math>n \log^2 n</math>
|<math>n \log^2 n</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|マージ
|[http://citeseer.ist.psu.edu/472101.html 実装例]
|-
|[[ヒープソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|選択
|
|-
|{{仮リンク|スムースソート|en|Smoothsort}}
|&mdash;
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|選択
|
|-
|[[クイックソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|<math>\log n</math>
|style="background-color:#ffdddd"|×
|{{Nowrap|パーティショニング}}
|メモリは[[コールスタック]]（素朴な実装では <math>\Omega(n)</math> になる）
|-
|[[イントロソート]]
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ddffdd"|<math>n \log n</math>
|<math>\log n</math>
|style="background-color:#ffdddd"|×
|混成
|メモリはコールスタック
|-
|{{仮リンク|ペイシェンスソート|en|Patience sorting}}
|&mdash;
|style="background-color:#ffdddd"|<math>n^2</math>
|<math>n</math>
|style="background-color:#ffdddd"|×
|挿入
|{{Nowrap|<math>O(n \log n)</math> 以内}}にすべての最長増加部分列を探す。
|-
|{{仮リンク|ストランドソート|en|Strand sort}}
|style="background-color:#ddffdd"|<math>n \log n</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|<math>n</math>
|style="background-color:#ddffdd"|○
|選択
|
|-
|{{Display none|キクウテンチ/}}[[奇偶転置ソート]]
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ddffdd"|○
|交換
|
|-
|[[シェアソート]]
|style="background-color:#ffdddd"|<math>n^{1.5}</math>
|style="background-color:#ffdddd"|<math>n^{1.5}</math>
|style="background-color:#ddffdd"|<math>1</math>
|style="background-color:#ffdddd"|×
|交換
|
|}

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

{|class="wikitable sortable" style="font-size:95%; margin-right:0px;"
|-style="line-height:1.4em; vertical-align:bottom; white-space:nowrap;"
!style="width:10.5em"|名称<br />!!style="width:14ex; white-space:nowrap;"|[[計算量|平均計算時間]]<br />!!style="width:21ex; white-space:nowrap;"|[[計算量|最悪計算時間]]<br />!!style="white-space:nowrap;"|[[メモリ]]使用量<br />!!style="width:3em"|{{Nowrap|[[安定ソート|安定性]]}}<br />!!style="white-space:nowrap;"|''n'' << 2<sup>''k''</sup>?<br />!!備考<br />
|-
|{{Display none|ハトノス/}}[[鳩の巣ソート]]
|style="background-color:#ddffdd"|<math>n+2^k</math>
|style="background-color:#ddffdd"|<math>n+2^k</math>
|<math>2^k</math>
|style="background-color:#ddffdd"|○
|○
|
|-
|[[バケットソート]]
|style="background-color:#ddffdd"|<math>n+k</math>
|style="background-color:#ffdddd"|<math>n^2</math>
|<math>nk</math>
|style="background-color:#ddffdd"|○
|×
|{{Nowrap|入力データは}}定義域に一様分布すると仮定
|-
|{{Display none|フンフカソエ/}}[[バケットソート|分布数えソート]]
|style="background-color:#ddffdd"|<math>n+2^k</math>
|style="background-color:#ddffdd"|<math>n+2^k</math>
|<math>n+2^k</math>
|style="background-color:#ddffdd"|○
|○
|
|-
|LSD [[基数ソート]]
|style="background-color:#ddffdd"|<math>nk/s</math>
|style="background-color:#ddffdd"|<math>nk/s</math>
|<math>n</math>
|style="background-color:#ddffdd"|○
|×
|
|-
| style="white-space:nowrap;" |MSD [[基数ソート]]
|style="background-color:#ddffdd"|<math>nk/s</math>
|style="background-color:#ddffdd"|<math>n(k/s)2^s</math>
|style="white-space:nowrap;"|<math>(k/s)2^s</math>
|style="background-color:#ffdddd"|×
|×
|
|-
|{{仮リンク|スプレッドソート|en|Spreadsort}}
|style="background-color:#ddffdd; white-space:nowrap;"|<math>nk/\log n</math>
|style="background-color:#ddffdd; white-space:nowrap;"|<math>n(k-\log n)^{0.5}</math>
|<math>n</math>
|style="background-color:#ffdddd"|×
|×
|{{Nowrap|n << 2<sup>k</sup>}} の場合の計算時間だが、それ以外の場合でもソート可能
|-
|{{Display none|キヤクシヤソウ/}}[[逆写像ソート]]
|style="background-color:#ddffdd"|<math>n</math> ?
|N/A
|<math>n</math> ?
|style="background-color:#ddffdd"|○
|×
|
|}

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

{|class="wikitable sortable" style="font-size:95%; margin-right:0px;"
|-style="line-height:1.4em; vertical-align:bottom; white-space:nowrap;"
!style="width:10.5em"|名称<br />!!style="width:14ex; white-space:nowrap;"|[[計算量|平均計算時間]]<br />!!style="width:21ex; white-space:nowrap;"|[[計算量|最悪計算時間]]<br />!!style="white-space:nowrap;"|[[メモリ]]使用量<br />!!style="width:3em"|{{Nowrap|[[安定ソート|安定性]]}}<br />!!style="white-space:nowrap;"|大小比較<br />!!備考<br />
|-
|[[ボゴソート]]
|<math>n \cdot n!</math>
|∞
|<math>1</math>
|style="background-color:#ffdddd"|×
|○
|平均時間はクヌースのシャッフルを使った場合
|-
|[[ボゴソート#ボゾソート|ボゾソート]]
|<math>n \cdot n!</math>
|∞
|<math>1</math>
|style="background-color:#ffdddd"|×
|○
|平均時間はボゴソートの約半分に漸近する。
|-
|[[ストゥージソート]]
|<math>n^{2.71}</math>
|<math>n^{2.71}</math>
|<math>\log n</math>
|style="background-color:#ffdddd"|×
|○
|
|-
| style="white-space:nowrap;" |[[スリープソート]]
|値の最大値×プロセス起動単位時間（実際には誤差あり）
|同左
|<math>n</math>?
|×
|?
|条件が特殊。実用の正確性が保証されない。
|-
| style="white-space:nowrap;" |[[ビーズソート|ビードソート]]
|N/A
|N/A
|&mdash;
|N/A
|×
|専用ハードウェアが必要
|-
|{{Display none|タンシユンハンケエキ/}}{{仮リンク|パンケーキソート|label=単純パンケーキソート|en|Pancake sorting}}
|<math>n</math>
|<math>n</math>
|<math>\log n</math>
|style="background-color:#ffdddd"|×
|○
|反転を定数時間で行えるものと仮定
|-
|[[ソーティングネットワーク]]
|<math>\log n</math>
|<math>\log n</math>
| style="white-space:nowrap;" |<math>n \log n</math>
|style="background-color:#ddffdd"|○
|×
|{{Nowrap|大きさ <math>O(n \log n)</math>}} の回路が必要。
|-
|[[バイトニックソート]]
|<math>\log^2 n</math>
|<math>\log^2 n</math>
| style="white-space:nowrap;" |<math>n \log^2 n</math>
|style="background-color:#ffdddd"|×
|×
|計算時間とメモリ使用量はソーティングネットワークとして実装したときの値
|-
|[[バッチャー奇偶マージソート]]
|<math>\log^2 n</math>
|<math>\log^2 n</math>
| style="white-space:nowrap;" |<math>n \log^2 n</math>
|style="background-color:#ffdddd"|×
|×
|計算時間とメモリ使用量はソーティングネットワークとして実装したときの値
|}

== 比較ソートアルゴリズムの最悪計算量の下界 ==

ソートを行う際、要素間の順序の決定を2要素の大小関係の比較処理のみを用いて行うことにする。この時、<math>n</math>要素からなるリストをソートするアルゴリズムの最悪比較回数は<math>\Omega(n \log n)</math>回となる。すなわち、どんな比較ソートアルゴリズムであっても入力によっては（一般的な入力に対しては）漸近的に<math>n \log n</math>回の比較が必要となる。

この理由を説明する。ある比較ソートアルゴリズムが与えられた際、様々な入力に対する処理の手順を二分決定木として表すことができる。内部ノードは2要素の比較処理を表し、内部ノードから子ノードへの2本の枝は比較結果に応じた処理を表す。また、葉は処理の終了を表す。この時、木の高さが最悪比較回数となる。<math>n</math>要素からなるリストが入力される時、どのような二分決定木を作ったとしても、木の高さが<math>\Omega(n \log n)</math>になることを示す。二分決定木の高さを<math>m</math>とした時、木の形によらず、葉の数は<math>2^m</math>以下になる。<math>n</math>要素からなるリストの（添字の）[[置換 (数学)|置換]]は<math>n!</math>個存在するが、任意の入力に対してアルゴリズムが正しい出力をするためには、<math>n!</math>個の異なるリストを入力した際、それらがすべて異なる葉に到達できるようにしなければならない。よって、葉の数は<math>n!</math>以上でなければならない。以上より、<math>n! \leq 2^m</math>である。[[スターリングの近似|スターリングの公式]]より<math>\left(\frac{n}{e}\right)^n < n!</math>なので、<math>\left(\frac{n}{e}\right)^n < 2^m</math>。よって、<math>m > \log_2 \left(\frac{n}{e}\right)^n = n(\log_2 n - \log_2 e)</math>。よって<math>m = \Omega(n \log n)</math>。

以上より、任意の比較ソートアルゴリズムの最悪計算量は<math>\Omega(n \log n)</math>となる。すなわち、比較ソートアルゴリズムの最悪計算量の下界は漸近的には<math>n \log n</math>となる。

マージソート、ヒープソートなどの比較ソートアルゴリズムの最悪計算量は<math>O(n \log n)</math>であるため、これらのアルゴリズムの最悪計算量は上記の下界と漸近的に一致していると言える。つまり、これらのアルゴリズムの最悪計算量は漸近的に最適である。

== メモリ使用パターンとインデックスソート ==
ソート対象の配列が主記憶を使い切るような（あるいは越えるような）大きさであった場合、より低速な[[補助記憶装置]]が使われるので、アルゴリズムのメモリ使用パターンが重要となる。そのような状況では、主記憶上ですべてソートできることを前提としたアルゴリズムは効率が極端に悪化する可能性がある。このような状況では、比較演算回数はあまり重要ではなくなり、ディスクとのメモリ領域の[[仮想記憶|スワップ]]回数が重要となる。したがって、なるべくスワップ回数を増やさないようにするために、配列全体を走査する回数や比較の局所性が比較回数よりも重要となる。

例えば、再帰型の[[クイックソート]]は主記憶上では性能が良いが、ソート対象の配列が主記憶に収まらない場合はスワップが頻繁に発生して、性能が極端に低下する。したがって、そのような場合は比較回数が多くても他のアルゴリズムを使った方がよい。

対策の一つとして、ソート対象の配列の要素が（[[関係データベース]]のような）複雑なレコードだった場合、その配列をそのままソートするのではなく、比較的小さいインデックスを生成して、インデックスの配列をソートするという方法がある。インデックスをソートすれば、元の配列のソートは一回の走査で可能であるが、インデックス経由でアクセスするだけならそれをする必要もない。インデックスは元の配列のレコードよりも小さいので、メモリに収まる可能性が高くなり、スワップ問題を削減することができる。この方式を「タグソート（tag sort）」などと呼ぶこともある<ref>[http://www.pcmag.com/encyclopedia_term/0,2542,t=tag+sort&i=52532,00.asp tag sort Definition] PCMAG.COM</ref>。

別の技法として、2つのアルゴリズムを組み合わせて、それぞれの利点を利用する方法がある。例えば、配列をチャンクに分割して個々のチャンクが主記憶上でソートできる大きさにする。チャンク内のソートはメモリ上で効率的に動作するソートアルゴリズムを使い、その結果を[[マージソート]]でマージする。これは、元の配列を単純にマージソートでソートするよりも効率が悪いが、全体をクイックソートでソートするよりもメモリ使用量が少なくてすむ。

これらの技法を組み合わせることも可能である。あまりにも巨大なデータをソートする場合、インデックスのソートにも複数のアルゴリズムを組み合わせて[[仮想記憶]]の性質に合うよう設計する必要がある。

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
{{参照方法|date=2013年5月}}

* [[ドナルド・クヌース|D. E. Knuth]], ''[[The Art of Computer Programming]], Volume 3: Sorting and Searching''.

==関連項目==
*[[照合]]
*[[検索]]
*[[選択アルゴリズム|選択]]
*[[データベース]]
*[[sort (UNIX)]]

== 外部リンク ==
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/algoen.htm Sequential and parallel sorting algorithms] - 各種アルゴリズムの説明と解析
* [http://www.dcc.uchile.cl/~rbaeza/handbook/sort_a.html Ricardo Baeza-Yates' sorting algorithms on the Web]
* [http://www.nist.gov/dads/ 'Dictionary of Algorithms, Data Structures, and Problems']
* [http://www.softpanorama.org/Algorithms/sorting.shtml Slightly Skeptical View on Sorting Algorithms] Softpanorama。古典的アルゴリズムについて論じ、クイックソートの代替となるアルゴリズムを提案。
* [http://www.azillionmonkeys.com/qed/sort.html Sorting Revisited]
* [http://www.cs.sunysb.edu/~algorith/ The Stony Brook Algorithm Repository] コード例と解説
* [https://arxiv.org/pdf/2209.06909.pdf William Cawley Gelling, Markus E. Nebel, Benjamin Smith and Sebastian Wild: "Multiway Powersort", (September 16, 2022)]

=== ソートアルゴリズムの視覚化 ===
* [http://thomas.baudel.name/Visualisation/VisuTri/ sort algorithm visualizer] - 11種類のソートアルゴリズムについて各種初期条件でのソートの様子を視覚化
* いくつかのソートアルゴリズムを視覚化した[http://homepage.mac.com/mihailod/atic/sorting.html Java applet]
* [http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html Sort Animation] - Javaアプレットによるバブルソート、挿入ソート、クイックソート、選択ソートのアニメーション図解
* [http://math.hws.edu/TMCM/java/xSortLab/ xSortLab] - 別のJavaアプレット。バブルソート、挿入ソート、クイックソート、選択ソート、マージソートをアニメーション化している。ソート対象を縦の棒で示している。
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/sortcontest/sortcontest.htm Sorting contest] - 8種類のソートアルゴリズムのアニメーションを一斉に実行でき、速度の違いを体感できる。

{{ソート}}
{{アルゴリズム}}

{{DEFAULTSORT:そおと}}
[[Category:ソート|*]]
[[Category:アルゴリズム]]
[[Category:データ処理]]