ソートの選択は、いくつかの特性に左右されます:時間計算量、安定性、インプレース メモリ使用、およびデータの性質。どのソートもすべての場面で最適とは限りません。
主な特性
- 安定的: 等しい要素は元の相対順序を保ちます(マルチキー ソートに必要)。
- インプレース: O(1) または O(log n) の追加メモリを使用します。
- 適応的: ほぼソート済みの入力では高速です。
| アルゴリズム | 平均時間 | 最悪時間 | 安定的 | インプレース |
|---|---|---|---|---|
| Insertion | O(n²) | O(n²) | はい | はい |
| Merge | O(n log n) | O(n log n) | はい | いいえ |
| Quick | O(n log n) | O(n²) | いいえ | はい |
| Heap | O(n log n) | O(n log n) | いいえ | はい |
# Most languages ship a tuned hybrid; prefer it in production
sorted(data, key=lambda x: x.priority) # stable Timsort in Python
特別な理由がない限り、ソートを手書きしないでください — ライブラリ ソート(Timsort、introsort)は実証済みのハイブリッドです。
ソートをデータと要件に合わせることで、無駄な時間と微妙なバグ(安定性の喪失など)の両方を回避できます。
トレードオフを理解することで、標準ライブラリが Timsort や introsort などのハイブリッドを選択した理由が説明されます。
この比較判断 — アルゴリズムを暗記するのではなく — は実際のエンジニアリングと面接が報酬を与えるものです。