小さな配列の最適化 — 小さいNで挿入ソートが勝つ理由

小さな配列のパラドックス

クイックソートやマージソートのようなO(n log n)アルゴリズムは漸近的にはO(n²)アルゴリズムより高速ですが、小さな配列では、よりシンプルなO(n²)アルゴリズムの方が実時間で実際に高速です。これが、すべての本番ソート実装がハイブリッドアプローチを使用する理由です。

シンプルなアルゴリズムが小さいNで勝つ理由

アルゴリズムの実際の実行時間は T(n) = c * f(n) で、cは定数係数、f(n)は計算量関数です。小さいnでは：

挿入ソート: T(n) = c₁ * n²
マージソート: T(n) = c₂ * n * log(n)

しかしc₁はc₂よりはるかに小さいです：

1. 再帰オーバーヘッドなし: 挿入ソートはシンプルなループを使用
2. 補助メモリなし: 一時配列の割り当てやコピーなし
3. より良いキャッシュ動作: 逐次メモリアクセスパターン
4. シンプルな分岐: 条件分岐が少なく、分岐予測が向上
5. 分割ステップなし: マージソートの分割とマージステップは小さな配列でもオーバーヘッドがある

クロスオーバーポイント

実装	クロスオーバー	使用閾値
Python（Timsort）	〜32-64要素	64（MIN_RUN）
Java（Arrays.sort）	〜47要素	47
C++（libstdc++）	〜16要素	16（_S_threshold）
V8 JavaScript	〜10要素	10
.NET	〜16要素	16

ハイブリッドアルゴリズムの動作

function hybridSort(arr, low, high):
  if high - low < THRESHOLD:
    insertionSort(arr, low, high)  // 小さなサブ配列にはシンプルなアルゴリズム
    return
  pivot = partition(arr, low, high)
  hybridSort(arr, low, pivot - 1)
  hybridSort(arr, pivot + 1, high)

通常、クロスオーバーは10〜64要素の間で、16–32が最も一般的な選択です。