JavaScriptとPythonでの実世界のソート

実際のプログラミング言語でのソート

主要なプログラミング言語が使用するソートアルゴリズムを理解することで、より効率的なコードを書き、パフォーマンス特性を予測できます。

JavaScript: V8のTimsort

2019年以降、V8（Chrome、Node.js）はArray.prototype.sort()にTimsortを使用しています。

主な特徴：

• 安定: ES2019以降のECMAScript仕様で必須
• 時間: O(n log n)最悪ケース、すでにソート済み配列ではO(n)
• 空間: 一時マージバッファにO(n)
• 閾値: 32要素未満のランに挿入ソートを使用

// JavaScriptのsortは安定で、内部的にTimsortを使用
const data = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Carol", age: 30 },
];
data.sort((a, b) => a.age - b.age);
// Alice(30)はCarol(30)の前に来る — 安定

Python: Timsort

Pythonのlist.sort()とsorted()はTimsortを使用しています。2002年にTim PetersがPython専用に発明しました。

主な機能：

• データ内の既存のソート済みランを識別
• 短いランを挿入ソートで拡張（最小ラン長〜32-64）
• ほぼソート済みデータに効率的なギャロッピングマージでランをマージ

# Pythonのsortは安定で適応的
data.sort(key=lambda x: x.department)
# 同じ部門内の要素は前の順序を保持

Java: デュアルピボットクイックソート + Timsort

Javaは2つの異なるアルゴリズムを使用：

• プリミティブ（int[]、double[]）: デュアルピボットクイックソート（不安定、プリミティブには安定性不要）
• オブジェクト（Object[]）: Timsort（安定、等しいオブジェクトが区別可能な可能性があるため）

C/C++: Introsort

• std::sort: Introsort — 安定性保証なし
• std::stable_sort: マージソート — 安定、O(n log n)、O(n)追加空間

効率的なコンパレータの書き方

// 悪い例: 文字列変換は遅い
arr.sort(); // まず文字列に変換！

// 良い例: 数値比較
arr.sort((a, b) => a - b);

// 良い例: 複数キーソート
arr.sort((a, b) => a.dept.localeCompare(b.dept) || a.name.localeCompare(b.name));

パフォーマンスのヒント

1. 可能な場合はソートを避ける: 上位k要素のみ必要な場合は部分ソートや選択アルゴリズムを使用
2. ソートに適したデータレイアウト: プリミティブの配列はキャッシュ局所性によりオブジェクト配列より高速にソート
3. ソート済み検出: TimsortとIntrosortはどちらもソート済み入力を検出；ソート前のシャッフルを避ける
4. カスタムコンパレータ: シンプルに保つ — O(n log n)回呼び出される