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