[解決済み] [Solved] JavascriptのArray.sortの実装は？

質問

JavaScriptはどのアルゴリズムで Array#sort() 関数を使用しますか？ 私は、バニラソートがどのアルゴリズムを使用しているかに興味があるだけです。

どのように解決するのですか？

WebKit (Chrome, Safari ...) を見てみたところ ソース . 配列の種類によって、異なるソート方法が使用されます。

数値配列 (またはプリミティブ型の配列) のソートには，C++ 標準ライブラリ関数 std::qsort これは、クイックソートのいくつかのバリエーションを実装しています（通常 イントロソート ).

非数値型の連続した配列 は文字列化され、マージソート(安定したソートを得るために)があればそれを使ってソートされるか、あるいは qsort マージソートがない場合

その他の型（非連続配列とおそらく連想配列）については、WebKit は以下のいずれかを使用します。 選択ソート (彼らは 「最小値ソート あるいは、AVLツリーでソートする場合もあります。残念ながら、ここでのドキュメントはかなり曖昧なので、実際にどの型にどのソートメソッドが使われているかを確認するには、コードパスをトレースする必要があります。

そして、次のような逸品があります。 このコメント :

// FIXME: Since we sort by string value, a fast algorithm might be to use a
// radix sort. That would be O(N) rather than O(N log N).

- 実際にこれを「修正」する人が、このコメントを書いた人よりも漸近的実行時間についてよく理解していて、以下のことに気づいていることを祈りましょう。 基数ソートには、もう少し複雑な実行時説明があります。 単純にO(N)であるよりも。

(元の回答の誤りを指摘してくれたphsourceに感謝します)。