JavaScript中数组排序sort深入理解（Array.prototype.sort）
JavaScript中数组排序sort深入理解（Array.prototype.sort）
疑问
最近在看算法书的时候看到C++中的sort方法，书中介绍是使用的快速排序。于是想起来自己天天都在写的JavaScript中的sort排序，它使用的是什么排序算法呢？各个浏览器使用的是同一种排序算法吗？
带着问题，打开了ECMA官方规范
规范中并没有写明具体使用的排序算法，只是说了JavaScript的sort方法（Array.prototype.sort）并不一定稳定！
Google Chrome浏览器
Google的Chrome浏览器的JavaScript引擎是：V8。
既然ECMA没有规定具体的排序算法，那具体实施应该是各个JavaScript引擎决定了。于是打开Chrome V8引擎的官方源码，V8引擎github源码。
第239行到254行：
code：
function InnerArraySort(array, length, comparefn) {
// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.
if (!IS_CALLABLE(comparefn)) {
comparefn = function (x, y) {
if (x === y) return 0;
if (%_IsSmi(x) && %_IsSmi(y)) {
return %SmiLexicographicCompare(x, y);
}
x = TO_STRING(x);
y = TO_STRING(y);
if (x == y) return 0;
else return x < y ? -1 : 1;
};
}代码中的注释明确写着：这个地方使用快速排序，但是当长度小于11的数组，使用的是插入排序。这也符合我们的正常观点，因为插入排序在数组长度小于一定值的时候是会比快速排序速度更快，快速排序在大规模数据的时候更有优势。插入排序是稳定的，快速排序是不稳定的。
知道了Chrome浏览器的排序算法。其他浏览器是不是也是这样呢？我们接着看。
Mozilla Firefox浏览器
Mozilla的Firefox浏览器的JavaScript引擎是：SpiderMonkey。
然后同样的方法，我们直接去看源码。源码地址
第2306行的注释：
code：
/*
* We need a temporary array of 2 * len Value to hold the array elements
* and the scratch space for merge sort. Check that its size does not
* overflow size_t, which would allow for indexing beyond the end of the
* malloc'd vector.
*/Mozilla的Firefox浏览器使用的是归并排序，归并排序是稳定的。
Safari浏览器
Safari浏览器的JavaScript引擎是：Nitro（JavaScriptCore ）。
第579行开始是这样写的：
code：
function comparatorSort(array, length, comparator){
let valueCount = compact(array, length);
mergeSort(array, valueCount, comparator); // 归并排序
}
function stringSort(array, length){
let valueCount = compact(array, length);
let strings = @newArrayWithSize(valueCount);
for (let i = 0; i < valueCount; ++i)
strings[i] = { string: @toString(array[i]), value: array[i] };
bucketSort(array, 0, strings, 0); // 桶排序
}Safari浏览器使用的是桶排序和归并排序，如果参数中含有comparator函数就使用归并排序，没有的话就使用桶排序。桶排序的稳定性不确定，归并排序是稳定的。
Microsoft Edge和IE浏览器
最后再来看看我们最难伺候的老大哥，老大哥浏览器的JavaScript引擎是：Chakra。