最近在学习JS，数组里有个方法sort()用来排序的，然后它可以有一个比较函数作为参数，我对于如何调用这个比较函数很困惑，书上只是简单说通过返回-1，0，1来确定升降排序，那内部的机制是什么样的，它用的什么排序方法

[CoooolChan]

[sNullp]

我猜是快排

[timonwong]

排序算法跟实现有关。v8对于小数组用了简单的排序算法，是稳定排序。其它数组用的quicksort
Firefox早期用quicksort, 现在用mergesort

[CoooolChan]

@timonwong 你屌爆了

[Golevka]

基于比较的排序算法不都是这样的么? 只要任意给两个元素a,b, 你能确定a>b还是a<b; 并且对于a<b, b<c, 总有a<c, 你就能用基于比较的排序算法对序列进行排序

[maxiujun]

v8的实现里面对length<=22的使用的是插入排序(稳定), 对于大于22的使用的是快速排序(非稳定),
可以参考: http://v8.googlecode.com/svn/trunk/src/array.js

[hooluupog]

我见过的一般是改进的快排，里面对递归的深度会有判断，当出现或即将出现快排最坏的情况时(O(n^2))，会转为堆排序。python和Go以及c++ stl有源码可以参考。

[timonwong]

@hooluupog
那种叫introsort吧，C++ STL上的 sort() 一般都是这种实现，稳定的 stable_sort() 还是用的 mergesort, 不过由于是实现相关的，不知道什么时候会变。

python 现在用 timsort (java现在也是，稳定排序，mergesort的一种)
go/pkg/sort就是很明显的quicksort

[hooluupog]

@timonwong Go 1.0是quicksort，1.1已经不是了，快排+堆排+插入 混合成的。http://golang.org/src/pkg/sort/sort.go

[sivacohan]

js的sort是错误。那个是基于字符串的比较

1 11 111 2 20 21

你可以尝试比较一下这个。

[otakustay]

@sivacohan ECMA262 V5关于sort的默认实现的原文在这里：

When the SortCompare abstract operation is called with two arguments j and k, the following steps are taken:

Let jString be ToString(j).
Let kString be ToString(k).
Let hasj be the result of calling the [[HasProperty]] internal method of obj with argument jString.
Let hask be the result of calling the [[HasProperty]] internal method of obj with argument kString.
If hasj and hask are both false, then return +0.
If hasj is false, then return 1.
If hask is false, then return –1.
Let x be the result of calling the [[Get]] internal method of obj with argument jString.
Let y be the result of calling the [[Get]] internal method of obj with argument kString.
If x and y are both undefined, return +0.
If x is undefined, return 1.
If y is undefined, return −1.
If the argument comparefn is not undefined, then
If IsCallable(comparefn) is false, throw a TypeError exception.
Return the result of calling the [[Call]] internal method of comparefn passing undefined as the this value and with arguments x and y.
Let xString be ToString(x).
Let yString be ToString(y).
If xString < yString, return −1.
If xString > yString, return 1.
Return +0.

标准就规定了要把数组中每个转成字符串再比较，因此无论如何这不能算是“错误”，从来没有人说数字组成的数组排序一定要按数字大小来吧？

[guchengf]

@sivacohan 正解，如果需要比较数值大小，还得有个比大小函数作为参数