ソートアルゴリズム

コンピュータサイエンスにおいて、ソートアルゴリズムとは、リストの要素を順序付けるアルゴリズムです。最もよく使用される順序は、数値順と辞書式順序、および昇順と降順です。効率的なソートは、入力データがソートされたリストにあることを必要とする他のアルゴリズム（検索アルゴリズムやマージアルゴリズムなど）の効率を最適化するために重要です。ソートは、データを正規化したり、人間が判読できる出力を生成するためにも役立ちます。

正式には、ソート アルゴリズムの出力は次の 2 つの条件を満たす必要があります。

1. 出力は単調な順序になります (必要な順序に従って、各要素は前の要素より小さく/大きくなりません)。
2. 出力は入力の順列（順序を変更しながらも、元の要素をすべて保持したもの）です。

一部のアルゴリズムは順次アクセス用に設計されていますが、最もパフォーマンスの高いアルゴリズムでは、データがランダム アクセスを可能にするデータ構造に格納されていると想定されています。

コンピューティングの黎明期から、ソート問題は多くの研究を集めてきた。おそらく、その単純で馴染みのある表現にもかかわらず、効率的に解くのが複雑だからだろう。1951年頃の初期のソートアルゴリズムの作者の一人に、ENIACとUNIVACに携わったベティ・ホルバートンがいた。^{[1] [2]}バブルソートは早くも1956年に分析された。^[3]漸近最適アルゴリズムは20世紀半ばから知られている。新しいアルゴリズムは現在でも発明されており、広く使用されているティムソートは2002年にさかのぼり、ライブラリソートは2006年に初めて公開された。

比較ソート アルゴリズムには、 Ω( n log n )回の比較という基本的な要件があります(入力シーケンスによっては、 n log nの倍数の比較が必要になる場合があります。ここで、 n はソートする配列の要素数です)。比較に基づかないアルゴリズム (カウント ソートなど) の方がパフォーマンスが向上する場合があります。

ソート アルゴリズムは、入門レベルのコンピュータ サイエンスの授業でよく取り上げられます。この問題に対するアルゴリズムが豊富に用意されているため、ビッグ O 記法、分割統治アルゴリズム、ヒープやバイナリ ツリーなどのデータ構造、ランダム化アルゴリズム、最良、最悪、平均ケースの分析、時間と空間のトレードオフ、上限と下限など、さまざまなコア アルゴリズムの概念をわかりやすく学ぶことができます。

小さな配列を最適に（比較とスワップを最小限にして）または高速に（つまり、マシン固有の詳細を考慮して）ソートすることは、まだ未解決の研究課題であり、解決策は非常に小さな配列（<20 要素）に対してのみ知られています。同様に、並列マシン上での最適な（さまざまな定義による）ソートは、未解決の研究課題です。

ソートアルゴリズムは次のように分類できます。

• 計算の複雑さ
  • リストのサイズの観点から見た最良、最悪、および平均の動作。一般的なシリアル ソート アルゴリズムの場合、良好な動作は O( n  log  n )、並列ソートは O(log ²  n )、悪い動作は O( n ² ) です。シリアル ソートの理想的な動作は O( n ) ですが、平均的な場合にはこれは不可能です。最適な並列ソートは O(log  n ) です。
  • 「インプレース」アルゴリズムにスワップします。
• メモリ使用量 (およびその他のコンピュータ リソースの使用)。特に、一部のソート アルゴリズムは「インプレース」です。厳密に言えば、インプレース ソートでは、ソートする項目以外に O(1) のメモリのみが必要です。場合によっては、O(log  n ) の追加メモリが「インプレース」と見なされます。
• 再帰: アルゴリズムの中には再帰的または非再帰的であるものもあれば、両方であるものもあります (例: マージ ソート)。
• 安定性: 安定したソート アルゴリズムは、等しいキー (つまり値) を持つレコードの相対的な順序を維持します。
• 比較ソートであるかどうか。比較ソートでは、比較演算子を使用して 2 つの要素を比較することによってのみデータが検査されます。
• 一般的な方法: 挿入、交換、選択、マージなど。交換ソートにはバブル ソートとクイック ソートが含まれます。選択ソートにはサイクル ソートとヒープソートが含まれます。
• アルゴリズムがシリアルかパラレルか。この説明の残りの部分は、シリアル アルゴリズムにほぼ専念し、シリアル操作を前提としています。
• 適応性: 入力の事前ソートが実行時間に影響するかどうか。これを考慮したアルゴリズムは適応型であることが知られています。
• オンライン: 挿入ソートなどのオンラインのアルゴリズムは、入力の一定のストリームをソートできます。

安定したソート アルゴリズムは、等しい要素を入力に現れるのと同じ順序でソートします。たとえば、右のカード ソートの例では、カードはランクでソートされ、スートは無視されます。これにより、元のリストの正しくソートされた複数の異なるバージョンが存在する可能性があります。安定したソート アルゴリズムは、次の規則に従って、これらのうちの 1 つを選択します。2 つの項目が等しいと判断された場合 (2 枚の 5 枚のカードなど)、それらの相対的な順序は保持されます。つまり、入力で一方が他方より前に来る場合、出力でも他方より前に来ます。

安定性は、同じデータ セットで複数の並べ替えを行っても順序を維持するために重要です。たとえば、名前とクラス セクションで構成される学生レコードが、最初に名前で、次にクラス セクションで動的に並べ替えられるとします。両方のケースで安定した並べ替えアルゴリズムが使用されている場合、クラス セクションによる並べ替え操作によって名前の順序は変更されません。不安定な並べ替えでは、セクションによる並べ替えによって名前の順序がシャッフルされ、学生のリストがアルファベット順でなくなる可能性があります。

より正式には、ソートされるデータはレコードまたは値のタプルとして表すことができ、ソートに使用されるデータの部分はキーと呼ばれます。カードの例では、カードはレコード (ランク、スーツ) として表され、キーはランクです。ソート アルゴリズムが安定しているのは、同じキーを持つ 2 つのレコード R と S があり、元のリストで R が S の前に現れる場合、ソートされたリストでも R が常に S の前に現れる場合です。

整数など、等しい要素が区別できない場合、またはより一般的には、要素全体がキーであるデータの場合、安定性は問題になりません。すべてのキーが異なる場合も、安定性は問題になりません。

不安定なソート アルゴリズムは、安定するように特別に実装できます。これを行う 1 つの方法は、キーの比較を人工的に拡張することです。これにより、同じキーを持つ 2 つのオブジェクトの比較は、元の入力リストのエントリの順序をタイブレーカーとして使用して決定されます。ただし、この順序を記憶するには、追加の時間とスペースが必要になる場合があります。

安定したソート アルゴリズムの 1 つの用途は、プライマリ キーとセカンダリ キーを使用してリストをソートすることです。たとえば、カードの手札を、スートがクラブ (♣)、ダイヤモンド ( ♦ )、ハート ( ♥ )、スペード (♠) の順で並び替え、各スート内ではカードがランク順に並び替えられるとします。これは、最初にカードをランク​​順に並び替え (任意のソートを使用)、次にスートで安定したソートを行うことで実行できます。

各スート内で、安定ソートは既に行われたランクによる順序付けを保持します。この考え方は任意の数のキーに拡張でき、基数ソートで利用されます。辞書式キー比較を使用することで、不安定ソートで同じ効果を実現できます。辞書式キー比較では、たとえば最初にスートで比較し、スートが同じ場合はランクで比較します。

この分析では、各キーの長さが一定であり、すべての比較、スワップ、およびその他の操作が一定時間で実行できることを前提としています。

伝説：

• n はソートするレコードの数です。
• 比較列には、各ケースの時間複雑度が指定されている場合、「最良」、「平均」、「最悪」のランキング分類があります。
• 「メモリ」は、アルゴリズムに必要な追加のストレージの量を示します。
• 記載されている実行時間とメモリ要件はビッグオー表記法で表されているため、対数の底は重要ではありません。
• log ² nという表記は(log n ) ^{2 を}意味します。

以下は比較ソートの表です。数学的分析により、比較ソートは平均してO ( n log n )以上のパフォーマンスを発揮できないことが示されています。^[4]

次の表は、整数ソートアルゴリズムと比較ソート以外のソートアルゴリズムについて説明しています。これらのアルゴリズムは、以下で説明する単位コストランダムアクセスマシンモデルを満たさない限り、 Ω ( n log n )に限定されません。^[12]

• 以下の複雑度は、ソートする項目がn個あり、キーのサイズがk、桁数がd、ソートする数値の範囲がr であると想定しています。
• それらの多くは、キー サイズが十分に大きいためすべてのエントリに一意のキー値があり、したがってn ≪ 2 ^kであり、ここで ≪ は「はるかに小さい」という意味である」という仮定に基づいています。
• 単位コストランダムアクセスマシンモデルでは、基数ソートなどの実行時間が のアルゴリズムでも、 は 以下に制限されるため、 Θ( n log n ) に比例した時間がかかります。また、ソートする要素の数が増えると、それらをメモリに格納するためにk を大きくする必要があります。 ^[13]${\displaystyle \scriptstyle n\cdot {\frac {k}{d}}}$${\displaystyle 2^{\frac {k}{d}}}$

Samplesort は、データを複数のバケットに効率的に分散し、複数のプロセッサにソートを渡すことで、非比較ソートを並列化するために使用できます。バケットは既に相互にソートされているため、マージする必要はありません。

実行時間が無制限のbogosortや実行時間がO ( n ^{2.7 ) の}stooge sortなど、一部のアルゴリズムは上で説明したものに比べて低速です。これらのソートは通常、アルゴリズムの実行時間をどのように見積もるかを示す教育目的で説明されています。次の表は、パフォーマンスが極端に低いか特殊なハードウェア要件のため、従来のソフトウェア コンテキストで実際に使用するのは非現実的なソート アルゴリズムの一部を示しています。

理論計算機科学者は、次のような追加の制約を前提として、 O ( nlogn )よりも優れた時間計算量 を実現する他のソートアルゴリズムを詳しく説明しています。

• ソルプのアルゴリズムは有限サイズのドメインからキーをソートするランダム化アルゴリズムで、O ( nloglogn )の時間とO ( n )の空間を要します。^[19]
• 期待時間とO ( n )のスペースを要するランダム整数ソートアルゴリズム。^[20]${\displaystyle O\left(n{\sqrt {\log \log n}}\right)}$
• 前述のアルゴリズムの著者の一人は、実数をソートする時間とO ( n )のスペースを要するアルゴリズムを発見したと主張している。 ^[21]さらに、入力に何らかの仮定を追加することなく、時間とO ( n )のスペースを達成するように変更できると主張している。${\displaystyle O\left(n{\sqrt {\log n}}\right)}$${\displaystyle O\left(n\log n/{\sqrt {\log \log n}}\right)}$

ソート アルゴリズムは多数存在しますが、実際の実装では少数のアルゴリズムが主流です。挿入ソートは小規模なデータ セットで広く使用されていますが、大規模データ セットでは、主にヒープソート、マージ ソート、クイックソートなどの漸近的に効率的なソートが使用されます。効率的な実装では通常、ハイブリッド アルゴリズムが使用され、全体的なソート用の漸近的に効率的なアルゴリズムと、再帰の下部にある小さなリスト用の挿入ソートが組み合わされます。高度に調整された実装では、Android、Java、Pythonで使用されるTimsort (マージ ソート、挿入ソート、および追加ロジック)や、一部のC++ ソート実装および.NETで(バリアント形式で) 使用されるintrosort (クイックソートとヒープソート) などのより洗練されたバリアントが使用されます。

固定間隔内の数値など、より制限されたデータの場合、カウント ソートや基数ソートなどの分布ソートが広く使用されています。バブル ソートとそのバリエーションは実際にはほとんど使用されませんが、教育や理論的な議論ではよく使用されます。

物理的にオブジェクトをソートする場合 (論文、テスト、本などをアルファベット順に並べるなど)、小さなセットでは直感的に挿入ソートが一般的に使用されます。大きなセットでは、多くの場合、最初に頭文字などでバケットに分け、複数のバケットに分けることで非常に大きなセットを実際にソートできます。多くの場合、オブジェクトを床や広い領域に広げるなど、スペースは比較的安価ですが、操作にはコストがかかり、特にオブジェクトを長距離移動する場合はコストがかかります。つまり、参照の局所性が重要です。マージソートも物理的なオブジェクトに実用的で、特に両手を使って各リストをマージできるため便利です。一方、ヒープソートやクイックソートなどの他のアルゴリズムは、人間の使用にはあまり適していません。スペースを残す挿入ソートの変種であるライブラリソートなどの他のアルゴリズムも、物理的な使用に実用的です。

最も単純なソートの 2 つは、挿入ソートと選択ソートです。どちらもオーバーヘッドが低いため、小さなデータでは効率的ですが、大きなデータでは効率的ではありません。挿入ソートは、比較が少なく、ほぼソートされたデータでのパフォーマンスが良いため、実際には選択ソートよりも高速であるため、実際には挿入ソートの方が好まれますが、選択ソートでは書き込みが少なくなるため、書き込みパフォーマンスが制限要因となる場合に使用されます。

挿入ソートは、小さなリストやほとんどソートされたリストに対して比較的効率的な単純なソートアルゴリズムであり、より洗練されたアルゴリズムの一部としてよく使用されます。これは、財布にお金を入れるのと同じように、リストから要素を1つずつ取り出し、新しいソートされたリストの正しい位置に挿入することによって機能します。 ^[22]配列では、新しいリストと残りの要素は配列のスペースを共有できますが、挿入はコストが高く、後続のすべての要素を1つずつシフトする必要があります。シェルソートは、挿入ソートの変種であり、より大きなリストに対してより効率的です。

選択ソートは、インプレース 比較ソートです。これはO ( n ² ) の複雑度を持つため、大きなリストでは非効率的であり、一般に類似の挿入ソートよりもパフォーマンスが悪くなります。選択ソートは単純であることで知られており、特定の状況ではより複雑なアルゴリズムよりもパフォーマンス上の利点があります。

このアルゴリズムは最小値を見つけ、それを最初の位置の値と交換し、リストの残りの部分に対してこれらの手順を繰り返します。^{[23]このアルゴリズムは}n回以上の交換を行わないため、交換コストが非常に高い場合に便利です。

実用的な一般的なソート アルゴリズムは、ほとんどの場合、平均時間計算量 (および一般的に最悪の場合の計算量) が O( n log n ) のアルゴリズムに基づいています。最も一般的なのは、ヒープソート、マージ ソート、クイックソートです。それぞれに利点と欠点がありますが、最も重要なのは、マージ ソートの単純な実装では O( n ) の追加スペースが必要になり、クイックソートの単純な実装では最悪の場合の計算量が O( n ² ) になることです。これらの問題は、より複雑なアルゴリズムを使用することで解決または改善できます。

これらのアルゴリズムはランダム データに対しては漸近的に効率的ですが、現実世界のデータに対する実用的な効率性を実現するために、さまざまな変更が行われます。まず、これらのアルゴリズムのオーバーヘッドはデータが小さいほど大きくなるため、多くの場合ハイブリッド アルゴリズムが使用され、データが十分に小さくなると挿入ソートに切り替わります。次に、これらのアルゴリズムは、すでにソートされたデータやほぼソートされたデータに対してはパフォーマンスが低下することがよくあります。これらは現実世界のデータでは一般的であり、適切なアルゴリズムを使用すれば O( n ) 時間でソートできます。最後に、これらのアルゴリズムは不安定になる場合もあり、ソートにおいては安定性が望ましい特性であることがよくあります。そのため、ティムソート(マージ ソートに基づく) やイントロソート(クイックソートに基づき、ヒープソートに戻る)などのより高度なアルゴリズムがよく使用されます。

マージソートは、すでにソートされたリストを新しいソートされたリストにマージすることの容易さを利用します。まず、すべての2つの要素を比較し（つまり、1と2、3と4...）、最初の要素が2番目の要素より後に来る場合はそれらを交換します。次に、結果として得られた2つのリストのそれぞれを4つのリストにマージし、さらにそれらの4つのリストをマージする、というように繰り返し、最終的に2つのリストが最終的なソートされたリストにマージされます。^{[24]ここで説明するアルゴリズムのうち、これは、最悪の場合の実行時間がO(} n log n )であるため、非常に大きなリストにうまく拡張できる最初のものです。また、ランダムアクセスではなくシーケンシャルアクセスのみを必要とするため、配列だけでなくリストにも簡単に適用できます。ただし、追加のO( n )の空間計算量があり、単純な実装では多数のコピーが必要になります。

マージソートは、プログラミング言語Python ^[25]やJava （ JDK7 ^[26]以降）の標準ソートルーチンで使用されている洗練されたアルゴリズムTimsortで使用されているため、実用的な実装で比較的最近人気が高まっています。マージソート自体は、Perl ^{[27]などの標準ルーチンであり、少なくとも2000年以降は}JDK1.3でJavaで使用されています。^[28]

ヒープソートは選択ソートのより効率的なバージョンです。これもまた、リストの最大（または最小）要素を決定し、それをリストの最後（または最初）に配置し、次にリストの残りを続行することによって機能しますが、特殊なタイプのバイナリツリーであるヒープと呼ばれるデータ構造を使用してこのタスクを効率的に実行します。^[29]データリストがヒープにされると、ルートノードが最大（または最小）要素であることが保証されます。ルートノードが削除されてリストの最後に置かれると、ヒープが再配置され、残っている最大の要素がルートに移動します。ヒープを使用すると、次の最大要素を見つけるのに、単純な選択ソートのように線形スキャンで O( n ) かかるのではなく、 O(log n ) 時間かかります。これにより、ヒープソートは O( n log n ) 時間で実行でき、これは最悪の場合の複雑さでもあります。

クイックソートは分割統治アルゴリズムであり、パーティション操作に依存しています。配列を分割するには、ピボットと呼ばれる要素が選択されます。^{[30] [31]}ピボットより小さいすべての要素はピボットの前に移動し、ピボットより大きいすべての要素はピボットの後に移動します。これは、線形時間でインプレースで効率的に実行できます。小さいサブリストと大きいサブリストは、次に再帰的にソートされます。これにより、平均時間計算量は O( n log n ) で、オーバーヘッドが低いため、このアルゴリズムは人気があります。クイックソートの効率的な実装 (インプレース分割を使用) は、通常、不安定なソートであり、いくぶん複雑ですが、実際には最も高速なソート アルゴリズムの 1 つです。適度な O(log n ) のスペース使用量と相まって、クイックソートは最も人気のあるソート アルゴリズムの 1 つであり、多くの標準プログラミング ライブラリで使用できます。

クイックソートに関する重要な注意点は、最悪の場合のパフォーマンスが O( n ² ) であることです。これはまれですが、単純な実装 (最初または最後の要素をピボットとして選択) では、ソートされたデータでこれが発生し、一般的なケースです。したがって、クイックソートで最も複雑な問題は適切なピボット要素を選択することです。一貫して不適切なピボットの選択は O( n ² ) のパフォーマンスを大幅に低下させる可能性がありますが、適切なピボットの選択は O( n log n ) のパフォーマンスをもたらし、これは漸近的に最適です。たとえば、各ステップで中央値がピボットとして選択される場合、アルゴリズムは O( n  log  n ) で動作します。ただし、中央値の中央値 選択アルゴリズムなどによる中央値の検索は、ソートされていないリストに対するO( n ) 操作であるため、ソートでかなりのオーバーヘッドが発生します。実際には、ランダムなピボットを選択すると、ほぼ確実に O( n  log  n ) のパフォーマンスが得られます。

O( n log n ) のパフォーマンスの保証が重要である場合、それを達成するための簡単な変更があります。Musser によるアイデアは、再帰の最大深度に制限を設けることです。^[32]その制限を超えると、ヒープソートアルゴリズムを使用してソートが続行されます。Musser は、制限は にすべきであると提案しました。これは、ランダムに順序付けられた配列で平均的に予想される最大再帰深度の約 2 倍です。 ${\displaystyle 1+2\lfloor \log _{2}(n)\rfloor }$

シェルソートは、1959 年にドナルド シェルによって発明されました。 ^[33]これは、順序がずれた要素を一度に複数の位置に移動することで、挿入ソートを改良したものです。シェルソートの背後にある概念は、挿入ソートは⁠ ⁠${\displaystyle O(kn)}$時間で実行されるというものです。ここで、k は 2 つの順序がずれた要素間の最大距離です。つまり、一般的にはO ( n ² ) で実行されますが、ほとんどがソートされていて、順序がずれている要素が少数であるデータの場合は、より高速に実行されます。したがって、最初に遠くにある要素をソートし、ソートする要素間のギャップを徐々に縮小することで、最終的なソートの計算がはるかに高速になります。1 つの実装は、データ シーケンスを 2 次元配列に配置し、次に挿入ソートを使用して配列の列をソートすると説明できます。

Shellsort の最悪ケースの時間計算量は未解決の問題であり、使用されるギャップ シーケンスに依存します。既知の計算量はO ( n ² )からO ( n ^4/3 ) および Θ( n log ² n ) の範囲です。これと、Shellsort がインプレースであり、比較的少量のコードしか必要とせず、コール スタックを使用する必要がないという事実を組み合わせると、組み込みシステムやオペレーティング システム カーネルなど、メモリが貴重である状況で役立ちます。

バブルソート、およびコームソートやカクテルソートなどのバリエーションは、単純で非常に非効率的なソートアルゴリズムです。分析が容易なため入門書ではよく見かけますが、実際に使用されることはほとんどありません。

バブルソートは単純なソートアルゴリズムです。このアルゴリズムはデータセットの先頭から始まります。最初の 2 つの要素を比較し、最初の要素が 2 番目の要素より大きい場合は、それらの要素を入れ替えます。データセットの最後まで、隣接する要素の各ペアに対してこれを続けます。次に、最初の 2 つの要素から再び開始し、最後のパスで入れ替えが発生しなくなるまで繰り返します。^[34]このアルゴリズムの平均時間と最悪の場合のパフォーマンスは O( n ² ) であるため、大規模で順序付けられていないデータセットのソートにはほとんど使用されません。バブルソートは、少数の項目をソートするために使用できます (漸近的な非効率性が高くないペナルティの場合)。バブルソートは、ほぼソートされている (つまり、要素が著しくずれていない) 任意の長さのリストに対して効率的に使用できます。たとえば、任意の数の要素が 1 つの位置だけずれている場合 (例: 0123546789 と 1032547698)、バブル ソートの交換により、最初のパスでそれらの要素が順序どおりに取得され、2 番目のパスですべての要素が順序どおりに検索されるため、ソートには 2 n時間しかかかりません。

^[35]

コームソートはバブルソートに基づく比較的単純なソートアルゴリズムで、1980年にWłodzimierz Dobosiewiczによって最初に設計されました。 ^[36]その後、Stephen LaceyとRichard Boxによって再発見され、 1991年4月にByte Magazineの記事で普及しました。基本的な考え方は、タートル、つまりリストの末尾近くの小さな値を削除することです。バブルソートでは、これらがソートを非常に遅くするためです。（ウサギ、つまりリストの先頭付近の大きな値は、バブルソートでは問題になりません）。これは、配列内で互いに一定の距離にある要素を最初に交換するのではなく、隣接する要素のみを交換し、次に選択した距離を縮小して通常のバブルソートとして機能するようにすることで実現します。したがって、シェルソートが、互いに一定の距離にある要素を交換する挿入ソートの一般化バージョンであると考えられる場合、コームソートは、バブルソートに適用された同じ一般化と考えることができます。

交換ソートはバブルソートと混同されることがあるが、実際にはこの 2 つのアルゴリズムは異なる。^{[37] [38]}交換ソートは、最初の要素をその上のすべての要素と比較し、必要に応じて交換することで、最初の要素が最終的なソート順として正しいことを保証する。次に、2 番目の要素についても同じことを行い、これを繰り返す。バブルソートのように、リストが既にソートされているかどうかを 1 回のパスで検出できるという利点はないが、最悪の場合でもバブルソートよりも一定倍高速になる (ソートするデータのパスが 1 つ少なくなり、比較の総数が半分になる)。単純な O( n ² ) ソートと同様に、非常に小さなデータ セットではかなり高速になるが、一般的には挿入ソートの方が高速である。

分散ソートとは、データが入力から複数の中間構造に分散され、その後、集められて出力に配置されるソート アルゴリズムを指します。たとえば、バケット ソートとフラッシュソートはどちらも分散ベースのソート アルゴリズムです。分散ソート アルゴリズムは、単一のプロセッサで使用することも、個々のサブセットが異なるプロセッサで個別にソートされてから結合される分散アルゴリズムとして使用することもできます。これにより、単一のコンピュータのメモリに収まらないほど大きなデータを 外部でソートできます。

カウンティング ソートは、各入力が特定の可能性の集合Sに属することがわかっている場合に適用できます。このアルゴリズムは、O(| S | + n ) 時間と O(| S |) メモリで実行されます。ここで、nは入力の長さです。サイズ | S | の整数配列を作成し、i番目のビンを使用して入力内のSのi番目のメンバーの出現回数をカウントします。次に、各入力は、対応するビンの値を増分することによってカウントされます。その後、カウンティング配列がループされ、すべての入力が順序どおりに並べられます。このソート アルゴリズムは、アルゴリズムを効率的に実行するにはS が適度に小さい必要があるため、使用できないことがよくありますが、非常に高速で、n が増加するにつれて優れた漸近動作を示します。また、安定した動作を提供するように変更することもできます。

バケット ソートは、配列を有限数のバケットに分割することでカウント ソートを一般化する分割統治ソート アルゴリズムです。各バケットは、異なるソート アルゴリズムを使用するか、バケット ソート アルゴリズムを再帰的に適用して個別にソートされます。

バケットソートは、データ セットの要素がすべてのバケットに均等に分散されている場合に最適に機能します。

基数ソートは、数字を個々の桁で処理してソートするアルゴリズムです。それぞれk桁のn個の数字は、O( n · k ) 時間でソートされます。基数ソートは、各数字の桁を最下位桁(LSD) から開始することも、最上位桁(MSD) から開始することもできます。LSD アルゴリズムは、まず安定ソートを使用して相対的な順序を維持しながら、最下位桁でリストをソートします。次に、次の桁でソートし、最下位桁から最上位桁までソートして、ソートされたリストを作成します。LSD 基数ソートでは安定ソートを使用する必要がありますが、MSD 基数ソート アルゴリズムでは必要ありません (安定ソートが必要な場合を除く)。インプレース MSD 基数ソートは安定ではありません。基数ソートでは、カウント ソートアルゴリズムが内部的に使用されるのが一般的です。小さなビンに挿入ソートを使用するなどのハイブリッドソート アプローチにより、基数ソートのパフォーマンスが大幅に向上します。

ソートする配列のサイズが使用可能なプライマリ メモリに近づくか超えると、(はるかに低速な) ディスクまたはスワップ領域を使用しなければならないため、ソート アルゴリズムのメモリ使用パターンが重要になり、配列が RAM に簡単に収まるときには比較的効率的であったアルゴリズムが実用的でなくなる可能性があります。このシナリオでは、比較の合計数は (比較的) 重要でなくなり、メモリのセクションをディスクにコピーまたはスワップする必要がある回数がアルゴリズムのパフォーマンス特性を左右する可能性があります。したがって、パスの数と比較のローカリゼーションが、比較の実際の数よりも重要になる可能性があります。これは、近くの要素同士の比較がシステム バス速度 (またはキャッシュを使用するとCPU速度) で行われ、ディスク速度と比較すると、事実上瞬時に行われるためです。

たとえば、一般的な再帰クイックソートアルゴリズムは、十分な RAM があればかなり妥当なパフォーマンスを提供しますが、配列の一部を再帰的にコピーするため、配列が RAM に収まらない場合は、ディスクとの間で低速のコピー操作や移動操作が多数発生する可能性があり、実用性が大幅に低下します。そのシナリオでは、より多くの合計比較が必要になる場合でも、別のアルゴリズムの方が適している場合があります。

この問題を回避する方法の 1 つは、複雑なレコード (リレーショナル データベースなど) が比較的小さなキー フィールドでソートされている場合に有効ですが、配列にインデックスを作成し、配列全体ではなくインデックスをソートすることです。(配列全体のソートされたバージョンは、インデックスから読み取る 1 回のパスで生成できますが、ソートされたインデックスがあれば十分なため、多くの場合、それも不要です。) インデックスは配列全体よりもはるかに小さいため、配列全体では収まらないメモリに簡単に収まる可能性があり、ディスク スワップの問題を効果的に排除できます。この手順は、「タグ ソート」と呼ばれることもあります。^[39]

メモリサイズの問題を克服する別の手法として、外部ソートを使用する方法があります。たとえば、2 つのアルゴリズムを組み合わせて、それぞれの長所を生かして全体的なパフォーマンスを向上させる方法があります。たとえば、配列を RAM に収まるサイズのチャンクに分割し、各チャンクの内容を効率的なアルゴリズム (クイックソートなど) を使用してソートし、結果をマージソートで使用されるものと同様のk方向マージを使用してマージします。これは、リスト全体に対してマージソートまたはクイックソートを実行するよりも高速です。^{[40] [41]}

テクニックを組み合わせることもできます。システム メモリを大幅に超える非常に大きなデータ セットをソートする場合、必要なスワッピングの量を減らすために、仮想メモリで適切に実行されるように設計されたアルゴリズムまたはアルゴリズムの組み合わせを使用して、インデックスをソートする必要がある場合があります。

関連する問題には、近似ソート（シーケンスを正しい順序から一定の範囲内でソートする）、部分ソート（リストのk 個の最小の要素のみをソートするか、 k 個の最小の要素を順序なしで検索する）、選択（k番目に小さい要素を計算する）などがあります。これらは、全ソートでは非効率的に解決できますが、より効率的なアルゴリズムが存在し、多くの場合、ソート アルゴリズムを一般化することで導き出されます。最も顕著な例は、クイックソートに関連するクイック選択です。逆に、一部のソート アルゴリズムは、選択アルゴリズムを繰り返し適用することで導き出すことができます。クイックソートとクイック選択は、両側で再帰するか（クイックソート、分割統治）、片側で再帰するか（クイック選択、減少統治）のみが異なる、同じピボット動作と見なすことができます。

ソート アルゴリズムの反対のようなものとして、シャッフル アルゴリズムがあります。これらは、乱数のソースを必要とする点で根本的に異なります。シャッフルは、ソート アルゴリズム、つまりランダム ソートによって実装することもできます。つまり、リストの各要素に乱数を割り当て、その乱数に基づいてソートします。ただし、これは実際には一般的には行われません。シャッフルには、フィッシャー イェーツ シャッフルという、よく知られたシンプルで効率的なアルゴリズムがあります。

ソート アルゴリズムは、多くの状況で順序を見つけるのに効果的ではありません。通常、要素に信頼できる比較機能がない場合 (投票システムなどのクラウドソーシングされた好み)、比較には非常にコストがかかる場合 (スポーツ)、またはすべての基準ですべての要素を一対一で比較することが不可能な場合 (検索エンジン) です。これらの場合、問題は通常ランキングと呼ばれ、比較またはランキングから推測される確率に従って、いくつかの基準で「最良」の結果を見つけることが目標です。一般的な例はチェスで、プレイヤーはElo レーティング システムでランク付けされ、ランキングはソート アルゴリズムではなくトーナメント システムによって決定されます。

• 照合 – 書面による情報を標準的な順序にまとめる
• Kソートシーケンス
• シュワルツ変換 – 計算されたキーでリストを効率的にソートするためのプログラミングイディオム
• 検索アルゴリズム – 検索問題を解決するアルゴリズム
• 量子ソート – 量子コンピュータのソートアルゴリズム

• Knuth, Donald E. (1998)、Sorting and Searching、The Art of Computer Programming、第3巻（第2版）、ボストン：Addison-Wesley、ISBN 0-201-89685-0
• セジウィック、ロバート(1980)、「コンピュータによる効率的なソート: 入門」、Computational Probability、ニューヨーク: Academic Press、pp. 101–130、ISBN 0-12-394680-8

Wikibookアルゴリズム実装には、ソートアルゴリズムに関するページがあります。

ウィキブックAレベル数学には、ソートアルゴリズムに関するページがあります。

ウィキメディア・コモンズには、ソートアルゴリズムに関連するメディアがあります。

• Wayback Machineのソートアルゴリズムアニメーション(2015 年 3 月 3 日アーカイブ)。
• 順次ソート アルゴリズムと並列ソート アルゴリズム – さまざまなソート アルゴリズムの説明と分析。
• アルゴリズム、データ構造、および問題の辞書 – アルゴリズム、テクニック、一般的な機能、および問題の辞書。
• ソートアルゴリズムに対するやや懐疑的な見方 - いくつかの古典的なアルゴリズムについて説明し、クイックソートアルゴリズムの代替案を推奨します。
• 6 分で 15 個のソート アルゴリズム (Youtube) – 6 分で 15 個のソート アルゴリズムを視覚化して「音声化」します。
• OEIS データベースの A036604 シーケンス、「数値のソート: n 個の要素をソートするために必要な比較の最小数」 – Ford–Johnson アルゴリズムによって実行されます。
• 有名な絵画に使用されているソートアルゴリズム (Youtube) – 多くの有名な絵画に使用されているソートアルゴリズムの視覚化。
• ソートアルゴリズムの比較 - Python timeit とGoogle Colab を使用して、主要なソートアルゴリズム 9 つに対する一連のテストを実行します。