ソート（sort）は、データの集合を一定の規則に従って並べること。
値の小さい順に並べる場合を昇順（ascending order）と言い、大きい順に並べることを降順（descending
order）と言う。
ここでは、独断と偏見に基づき、学習または実用性の観点から有効なアルゴリズムを挙げています。
| 名称 | 平均 計算時間 |
最悪 計算時間 |
メモリ 使用量 |
安定 | 手法 | 備考 |
|---|---|---|---|---|---|---|
| バブルソート | — | O(n2) | O(1) | ○ | 交換 | 同等性能のアルゴリズムとして、ノームソート（バブルソートと挿入ソートのハイブリッド）、シェーカーソート（カクテルソート）、奇偶転置ソートがある。 |
| コームソート | O(n log n) | O(n log n) | O(1) | × | 交換 | コードサイズが小さくて済む。 |
| 挿入ソート | O(n + d) | O(n2) | O(1) | ○ | 挿入 | ほとんど整列されたデータに対しては高速、d は置換群の反転数で、O(n2) |
| シェルソート | — | O(n log2 n) | O(1) | × | 挿入 | |
| 2分木ソート | O(n log n) | O(n log n) | O(n) | ○ | 挿入 | データの2分木（平衡2分探索木）を構築し、2分木を使ってソート |
| ライブラリソート | O(n log n) | O(n2) | O(n) | ○ | 挿入 | 間隔を空けたリスト要素間で行う挿入ソート |
| マージソート | O(n log n) | O(n log n) | O(n) | ○ | マージ | マージソートの空間を最適化した手法として、メモリ使用量の低減に貢献する 「In-place マージソート」がある |
| クイックソート （スタックソート） |
O(n log n) | O(n2) | O(log n) | × | 分割 | 単純な実装ではメモリ使用量が O(n)
になる。 ピボット値として中央値を使えば、最悪時間が O(n log n)。 |
| 選択ソート | O(n2) | O(n2) | O(1) | × | 選択 | 安定ソートとしても実装可能 |
| ヒープソート | O(n log n) | O(n log n) | O(1) | × | 選択 | クイックソートとヒープソートのハイブリッドとして「イントロソート」がある |
| スムースソート | — | O(n log n) | O(1) | × | 選択 | ヒープソートの小型版 |
| バケットソート | O(n * k) | O(n2 * k) | O(n * k) | ○ | ※1、※2 | |
| 分布数えソート | O(n + 2k) | O(n + 2k) | O(n + 2k) | ○ | ※1、※2 | |
| LSD 基数ソート | O(n * k/s) | O(n * k/s) | O(n) | ○ | ||
| MSD 基数ソート | O(n * k/s) | O(n * (k/s) * 2s) | O((k/s) * 2s) | × |
※1…要素の定義域分の外部記憶が必要。
※2…入力データは定義域に一様分布すると仮定
本表において、n はデータの個数、k はキーの長さ、s は実装で使われるチャンクのサイズ
…と、まずは Wikipedia の参照でお茶を濁しておきます。
データの比較に基づいてソートを行う場合、最悪計算時間は、最低でもO(n log n)必要なことが知られている。
安定ソート（stable sort -
ソートの安定性）とは、同等なデータのソート前の順序が、ソート後も保存されるものをいう。例えば、身長/体重のデータを、まず身長順に整列し、次に体重順で並べ替えたとき、安定ソートを用いると、同じ体重のデータは身長順で並ぶ。
レコードのような複数キーのデータにおいては十分に考慮する必要があるが、単一キー（値の単純な並べ替え）においては特に考慮する必要はない。
2008/07/21: 作成