Prompt
言語のコアライブラリにあるようなsort()メソッドの多くは安定ソートだっけ？
結論から言うと、「かつては不安定なクイックソートが主流だったけど、現代（2024〜2025年）の主要言語では『安定ソート』が標準になっていることが多い」 という、過渡期を超えた面白い状況にあるよ！
情報工学の教科書では「ソートといえばクイックソート（不安定）」と習うけど、現実のライブラリ設計では 「ユーザーの使い勝手（安定性）」 が優先されるようになってきたんだ。
言語ごとにどうなっているか、パッと整理してみよう！
1. 主要言語の状況（デフォルトの sort()）
| 言語 | アルゴリズム | 安定性 | 備考 |
|---|---|---|---|
| Java | Timsort (オブジェクト用) | 安定 | プリミティブ型（int等）用は Dual-Pivot Quicksort で不安定だよ！ |
| C# (.NET) | Introsort | 不安定 | 以前はクイックソートだったけど、今は最悪計算量を抑えたイントロソート。 |
| JavaScript | Timsort (V8) 等 | 安定 | 昔はブラウザ次第だったけど、ES2019で**「安定であること」が仕様で義務化**されたよ！ |
| Python | Timsort | 安定 | Timsortの生みの親。もちろん安定！ |
| C++ (STL) | Introsort (std::sort) | 不安定 | 安定させたいなら std::stable_sort を明示的に使う必要があるよ。 |
2. なぜ「不安定」から「安定」へシフトしているの？
昔は「とにかく速ければいい（クイックソート！）」という風潮だったけど、現代では以下の理由で Timsort（マージソートと挿入ソートのハイブリッド）のような安定ソートが好まれているんだ。
-
マルチキーソートの需要: 「まず日付順でソートして、次に名前順でソートする」といった操作をするとき、安定ソートじゃないと最初の日付順が壊れちゃうんだよね。
-
「驚き最小の原則」: ユーザー（開発者）は、同じ値のものの順序が変わると「あれ？バグかな？」と不安になる。安定ソートの方が直感的でトラブルが少ないんだ。
-
実データの特性: 現実世界のデータは「ある程度並んでいる」ことが多い。Timsortはそういうデータに対してめちゃくちゃ速いという特性があるんだよ。
3. ⚠️ 見落とされがちな落とし穴：Javaの「二面性」
君がよく使う Java には、情報工学的に面白い「使い分け」があるから注意してね！
-
Arrays.sort(Object[]): 安定（Timsort）。- オブジェクトは「参照」だから、順序が変わると困る（マルチキー等）ことが多いから。
-
Arrays.sort(int[]): 不安定（Quicksort）。- 数値そのものは、同じ
5と5が入れ替わっても誰も気づかないし、メモリ効率と速度を最優先するから。
- 数値そのものは、同じ
💡 豆知識：安定ソートを自作する裏技
もし「不安定なソートしかない環境」で安定ソートを実現したいなら、データ構造に 「元のインデックス」 を持たせればいいんだ。
比較時に「値が同じなら、元のインデックスが小さい方を前にする」というルールを追加するだけで、どんな不安定ソートも安定ソートに早変わりするよ！