ソートアルゴリズム

ソートアルゴリズムとは

ソートアルゴリズムは、データを昇順・降順に並べ替えるアルゴリズムの総称である。JavaScript の Array.prototype.sort() は内部的に TimSort (マージソート + 挿入ソートのハイブリッド) を使用している。

主要なアルゴリズム

アルゴリズム	平均	最悪	安定	特徴
バブルソート	O(n²)	O(n²)	✅	教育用、実用には遅い
挿入ソート	O(n²)	O(n²)	✅	小さい配列に高速
マージソート	O(n log n)	O(n log n)	✅	安定、追加メモリ O(n)
クイックソート	O(n log n)	O(n²)	❌	実用で最速、インプレース
TimSort	O(n log n)	O(n log n)	✅	JS, Python の標準
ヒープソート	O(n log n)	O(n log n)	❌	インプレース、キャッシュ効率が低い

TypeScript での使用

// 数値のソート (デフォルトは文字列比較なので注意)
[10, 2, 30].sort(); // [10, 2, 30] ❌ 文字列として比較
[10, 2, 30].sort((a, b) => a - b); // [2, 10, 30] ✅

// オブジェクトのソート
users.sort((a, b) => a.age - b.age); // 年齢の昇順
users.sort((a, b) => a.name.localeCompare(b.name)); // 名前の辞書順

// 安定ソート (ES2019 で保証)
// 同じキーの要素の相対順序が保持される

安定ソート vs 不安定ソート

入力: [{name: "Alice", age: 30}, {name: "Bob", age: 30}, {name: "Carol", age: 25}]

安定ソート (age でソート):
  Carol(25), Alice(30), Bob(30)  ← Alice と Bob の順序が保持

不安定ソート:
  Carol(25), Bob(30), Alice(30)  ← Alice と Bob の順序が変わる可能性

計算量の直感

計算量	100 万件の比較回数
O(n²)	1 兆回 (数時間)
O(n log n)	2,000 万回 (ミリ秒)
O(n)	100 万回

DynamoDB でのソート

DynamoDB はソートキー (SK) でアイテムを自動的にソートする。クエリ結果は SK の昇順で返され、ScanIndexForward: false で降順にできる。

実務での選択

JavaScript の Array.prototype.sort() (TimSort) がほとんどのケースで最適。自前でソートアルゴリズムを実装する必要はない。

さらに掘り下げるなら関連書籍が参考になる。