Array.prototype.sort について

JavaScriptの配列にはsortメソッドがあり配列のソートを実行することができるけど、この配列のソートの中の実装はどうなっているのかという話。v8における配列ソートについての記事が大変参考になりました。

Chrome(V8)の実装はarray.jsにあり、配列の要素数が10以下の場合はInsertion sortを使い、それ以上の場合はQuicksortを利用する。Insersion sortの計算量はO(n^2)であるけど、少ない要素数の場合はQuicksortなどより高速になるらしい。直近のcommmitを見る限りだと、Chrome 69か70あたりでTimsortに置き換えるつもりらしい。TimsortはaverageがO(n log n)で、最悪でもO(n log n)の計算量で済む。QuicksortをTimSortに置き換えるつもりに至った経緯などは調べてない（ので間違ってるかも）。Quicksortはstableではないソートであるけど、Timesortはstable sortになるので、その辺りの挙動は変わってくるかもしれない。

Firefox(Gecko)の実装はArray.jsあたりと思われる。最初にnative codeでの実装（js/src/builtin/Array.cpp）を試すようになっている。ざっと見た感じではMerge sortが使われている。Merge sortはaverageでO(n log n)の計算量になる。TypedArrayの実装ではQuicksortなどが使われている。

Safari(Webkit)の実装はArrayPrototype.jsあたりと思われる。What is the sorting algorithm behind a Javascript Array.sort method?あたりの話だと、以前はSelection sortが使われていたそうだが、現在の実装を見る限りではMerge sortが使われているようだ。

Microsoft Edege(ChakraCore)の実装は（EntrySortメソッドから入ってなんやかんやあって）JavascriptArray.cppあたりになると思われる。配列の要素数が512個より大きい場合はQuicksortを使用する。512個以下の場合は見た感じBinary Insertion Sortであると思われる。

という感じで、ざっとそれぞれのブラウザの実装を見たのですけど、Quicksort、Merge sort、Timsortで実装されているのがわかった。実装の違いはあるにせよ、ビック・オー的にはO(n log n)とみなしても問題ないのだろうと思う。

ChromeのsortがTimsortになると各ブラウザのsortの返りはstableになると思われるが、ECMA2015の仕様では、sortメソッドにおいてstable sortである必要はないとされている。なので、実際にはstableな状態で返ってくるとしても、JavaScriptのsortはstable sortではないと認識しておいた方がいい。

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order). If comparefn is not undefined, it should be a function that accepts two arguments x and y and returns a negative value if x < y, zero if x = y, or a positive value if x > y.
https://www.ecma-international.org/ecma-262/6.0/#sec-array.prototype.sort

そしてこれは蛇足で調べ中に知ったのですが、[100, 20, 0].sort()みたいに、compare function なしでソートを実行すると、デフォルトでUnicodeコードポイントの昇順にソートにされる（文字列として評価される）。だから結果は[0, 100, 20]となる。TypedArrayの場合は数値として評価される。

The following version of SortCompare is used by %TypedArray%.prototype.sort. It performs a numeric comparison rather than the string comparison used in 22.1.3.24. SortCompare has access to the comparefn and buffer values of the current invocation of the sort method.
https://www.ecma-international.org/ecma-262/6.0/#sec-%typedarray%.prototype.sort

その他参考。

以上。