javascript - Javascript Array.sort实现？(Javascript Array.sort implementation?)

Question

Which algorithm does the JavaScript Array#sort() function use?(JavaScript Array#sort()函数使用哪种算法？)

I understand that it can take all manner of arguments and functions to perform different kinds of sorts, I'm simply interested in which algorithm the vanilla sort uses.(我知道可以使用各种形式的参数和函数来执行不同种类的排序，我只是对香草排序使用哪种算法感兴趣。)   ask by latortuga translate from so

Answer 1

I've just had a look at the WebKit (Chrome, Safari …) source .(我刚刚看过WebKit（Chrome，Safari…） 源 。)

Depending on the type of array, different sort methods are used:(根据数组的类型，使用不同的排序方法：)

Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function std::qsort which implements some variation of quicksort (usually introsort ).(数值数组 （或原始类型的数组）使用C ++标准库函数std::qsort进行排序，该函数实现了quicksort （通常是introsort ）的某些变体。)

Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or qsort if no merge sort is available.(非数字类型的连续数组使用mergesort进行字符串化和排序（如果可用）（以获得稳定的排序），如果没有合并排序，则使用qsort排序。)

For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call “min” sort ) or, in some cases, it sorts via an AVL tree.(对于其他类型（非连续数组，大概是关联数组），WebKit使用选择排序 （它们称为“ min”排序 ），或者在某些情况下，它通过AVL树进行排序。)

Unfortunately, the documentation here is rather vague so you'd have to trace the code paths to actually see for which types which sort method is used.(不幸的是，这里的文档含糊不清，因此您必须跟踪代码路径以实际查看使用哪种类型的排序方法。)

And then there are gems like this comment :(再就是像宝石此评论 ：)

// 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).

– Let's just hope that whoever actually “fixes” this has a better understanding of asymptotic runtime than the writer of this comment, and realises that radix sort has a slightly more complex runtime description than simply O(N).(–我们只希望真正“解决”此问题的人比这篇评论的作者对渐近运行时有更好的理解，并意识到基数排序比简单的O（N） 稍微复杂一些。)

(Thanks to phsource for pointing out the error in the original answer.)(（感谢phsource指出了原始答案中的错误。）)