JavaScriptのソートは何ソート？

https://fec-kansai.connpass.com/event/396639/

Transcript

1. JavaScriptのsortは何ソート？ Keisuke Ikeda @ike̲keichan 2026.07.29 Kansai Frontend Meetup #2
2. 自己紹介 Keisuke Ikeda ・東京と関西（大阪&京都）の2拠点生活中 ・Maybe Software Engineer ・テックコミュニティに積極参加 - TSKaigi 2025,2026 / フロカン関西 2025,2026 / ReactTokyoフェス 2026 スタッフ - TSKaigi 2025,2026 に登壇 - 他にもテックイベントに学生時代から多数参加 @ike̲keichan 02/18
3. アルゴリズムとJSのsort ソートアルゴリズムと JS の sort @ike̲keichan 03/18
4. アルゴリズムとJSのsort みなさん、 Array.prototype.sort を使用したことありますか？ @ike̲keichan 04/18
5. アルゴリズムとJSのsort 何気なく呼んでいる sort() const scores = [50, 3, 91, 27, 8]; scores.sort((a, b) => a - b); // [3, 8, 27, 50, 91] @ike̲keichan 05/18
6. アルゴリズムとJSのsort ソートアルゴリズムって n 種類あんねん ・O(n²) 系 - バブルソート、シェーカーソート、選択ソート、挿入ソート、ノームソート など ・O(n log n) 系 - マージソート、クイックソート、ヒープソート、シェルソート、イントロソート、 TimSort、Powersort など ・その他 - バケットソート、基数ソート、計数ソート（非比較・条件付きで O(n) 級）、ボゴソート、 スリープソート など @ike̲keichan 06/18
7. アルゴリズムとJSのsort では、 Array.prototype.sort のソートアルゴリズムは何でしょうか？ @ike̲keichan 07/18
8. アルゴリズムとJSのsort エンジンによって違う ・各JavaScriptエンジンはECMAScriptに基づいてJavaScriptの互換性をおお よそ担保している。 ・しかし、実装の仕方までは指定されていないので、 JavaScriptエンジンに よって実装が異なる。 ・つまり、実行時のパフォーマンスも微妙に異なる。 ・今回はArray.prototype.sortの主要Webブラウザでの実装の違いを見る。 @ike̲keichan 08/18
9. アルゴリズムとJSのsort ブラウザ / ランタイムとエンジンの対応図 @ike̲keichan 09/18
10. 3大エンジンのsort実装 3大エンジンの sort 実装 @ike̲keichan 10/18
11. 3大エンジンのsort実装 V8：TimSort（~2026/04/20） ・仕組み：挿入ソート × マージソートのハイブリッド - 2002年、PythonのTim Peters氏が開発したことから由来 - 並び済みの区間（run）を見つけ、短い run は挿入ソートで整え、run を順にマージ - 「実データは部分的に並んでいる」ことを突く適応型 - 最悪 O(n log n) / 既ソートなら O(n) / 安定 ・実装言語：V8独自言語 V8 Torque ・V8 は 7.0 / Chrome 70（2018年）でクイックソート（不安定）から移行 @ike̲keichan 11/18
12. 3大エンジンのsort実装 V8：Powersort（2026/04/21~） ・仕組み：TimSort の「run をマージする順番」だけを置き換えたもの - 2018年、Munro & Wildが提案 - 経験則ではなく、ほぼ最適な順序を計算で決める - run 検出・挿入ソートは TimSort と同じ - 最悪 O(n log n) / 既ソートなら O(n) / 安定 ・実装言語：V8独自言語 V8 Torque ・Chrome 149（2026年6月）から適用。狙いは速度ではなく、TimSort の「微 妙すぎる」スタック不変条件をなくすこと（コミットメッセージより） @ike̲keichan 12/18
13. 3大エンジンのsort実装 JavaScriptCore：Powersort ・仕組み：現在のV8と同じアルゴリズム ・実装言語：C++（2024年にJS実装から移行） ・Python が 3.11（2022年）で TimSort のマージ順を Powersort に置き換えた のが先例。JSC は 2025年2月、V8 は 2026年4月にこれに続いた。両者の違 いは実装言語（C++ / V8 Torque）だけになった。 @ike̲keichan 13/18
14. 3大エンジンのsort実装 SpiderMonkey：マージソート ・仕組み：ボトムアップ型のマージソート - 4要素ずつ挿入ソートで整えてから、幅を倍にしながらマージ - 配列長 8 以下は挿入ソートのみ - run 検出をしないので構造が単純 - 最悪 O(n log n) / 既ソートでも O(n log n) / 安定 ・実装言語：C++ + JIT トランポリン（Firefox 126 / 2024年に self-hosted JS から移植） ・実装者自身がバグトラッカーで「うちのアルゴリズムは最も効率的とは 言えない」と明言 @ike̲keichan 14/18
15. 3大エンジンのsort実装 3エンジンまとめ @ike̲keichan 15/18
16. 3大エンジンのsort実装 まとめ ・アルゴリズム観点では、実データに適応的な Powersort 勢（V8・ JSC）が理論上一歩リード ・当然だが、必ずV8・JSCが早いとは限らない - 実際のソート対象によって異なる - 当然他の動作もパフォーマンスに影響 - あくまで１観点として覚えておくと面白い @ike̲keichan 16/18
17. 参考文献 ソースコード・コミット ・V8: array-sort.tq（PowerSort） ・V8: array-sort.tq（TimSort・旧） ・JavaScriptCore: StableSort.h ・SpiderMonkey: Sorting.h ・SpiderMonkey: Sorting-inl.h ・V8：「Sorting: TimSort --> PowerSort」2026-04 ・WebKit：「Improve arrayStableSort using Powersort」2025-02 ・WebKit：「[JSC] Rewrite Array#sort」2024-04 @ike̲keichan 17/18
18. 参考文献 文献 ・Jan de Mooij「Reimplement Array.prototype.sort with a JIT trampoline」, Mozilla Bugzilla, 2024年, https://bugzilla.mozilla.org/show̲bug.cgi?id=1884360 ・J. Ian Munro, Sebastian Wild「Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs」, ESA 2018, 2018年, https://arxiv.org/abs/1805.04154 ・Simon Zünd「Getting things sorted in V8」, V8 Blog, 2018年, https://v8.dev/blog/array-sort ・Tim Peters「listsort.txt」, CPython, 2002年, https://github.com/python/cpython/blob/main/Objects/listsort.txt @ike̲keichan 18/18