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 に置き換えるつもり
