Bubble
安定性: Stable
計算量: Avg O(n^2)
1950年代に広まった古典手法。隣接要素を比較して入れ替えを繰り返し、端へ泡のように移動させます。
アルゴリズムの簡単な説明
比較ソート（Comparison sort）
Insertion
安定性: Stable
計算量: Avg O(n^2)
1950年代から使われてきた定番。整列済み部分に要素を差し込み、局所的に少しずつ並べ替えます。
Selection
安定性: Unstable
計算量: Avg O(n^2)
1950年代に登場した古典。未整列部分から最小を選び、先頭へ置く操作を繰り返します。
Quick
安定性: Unstable
計算量: Avg O(n log n)
1960年代にHoareが提案。ピボットで分割し、左右を再帰的に整列する高速な分割統治法です。
Merge
安定性: Stable
計算量: Worst O(n log n)
1945年ごろに提案。配列を分割して整列し、安定なマージで戻す分割統治法です。
Heap
安定性: Unstable
計算量: Worst O(n log n)
1964年にWilliamsが提案。ヒープ構造で最大/最小を取り出しながら並べ替えます。
Shell
安定性: Unstable
計算量: Avg O(n^2)
1959年にShellが提案。間隔を空けた挿入ソートを繰り返し、最終的に通常挿入へ収束します。
Intro
安定性: Unstable
計算量: Worst O(n log n)
1997年にMusserが提案。クイックの平均性能を使いつつ、深さが増えるとヒープに切替えます。
Tim
安定性: Stable
計算量: Worst O(n log n)
2002年にPetersが提案。局所的な並び（ラン）を見つけて挿入・マージで統合する実用型です。
Comb
安定性: Unstable
計算量: Avg O(n^2)
1991年にDoboxらが提案。比較間隔を広げたバブル改良で、ギャップを縮めながら整列します。
Cocktail
安定性: Stable
計算量: Avg O(n^2)
1980年代に知られた手法。前後に往復しながらバブル操作を行い、両端を詰めていきます。
Gnome
安定性: Stable
計算量: Avg O(n^2)
2000年代に名称が広まりました。逆順を見つけたら一歩戻る操作で局所的に整列します。
Odd-even
安定性: Stable
計算量: Avg O(n^2)
1970年代から知られる方法。奇数・偶数インデックスのペアを交互に比較し、並列化に向きます。
Bitonic
安定性: Unstable
計算量: O(n log^2 n)
1968年にBatcherが提案。ビトニック列を作って比較ネットワークで整列します。
Odd-even merge
安定性: Unstable
計算量: O(n log^2 n)
1968年にBatcherが提案。奇偶マージネットワークで規則的に比較し、並列実装に向きます。
非比較ソート（Non-comparison sort）
Counting
安定性: Stable
計算量: O(n+k)
1950年代に普及。値の出現回数を数えて位置を決める非比較型で、範囲が狭いと高速です。
Radix
安定性: Stable
計算量: O(d(n+k))
19世紀末から概念があり、1950年代に実用化。桁ごとに安定ソートを繰り返します。
Bucket
安定性: Stable
計算量: Avg O(n+k)
1956年ごろの提案。範囲を区切ってバケツに分配し、各バケツを個別に整列します。
特殊
Bogo
安定性: Unstable
計算量: Unbounded
1980年代にジョークとして流行。無作為に並べ替え、偶然整列するのを待ちます。
Stalin
安定性: Not a full sort
計算量: O(n)
2010年代のジョーク。順序を乱す要素を粛清して捨て、残った列だけが整列済みになります。