零、简述：
最近在工作中，发现一个排序错乱的bug，经排查发现是node不同版本下，sort表现不一致导致。为了一探究竟，打开v8的sort源码摸索了半天、结合网上搜索到的文章终于整明白了，此文做个简单总结。
文中会附上自己用以解决原生不稳定排序问题的方案
一、发现问题：
const list = new Array(20).fill(1).map((n, idx) => ({sort: 0, idx: idx}));
list.sort((p, n) => p.sort - n.sort);
console.log(list);
// node 10 输出： [ 10, 0, 2, 3, 4, 5, 6, 7, 8, 9, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]
// node 12 输出：[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]
可以看到，node 10 输出了一个出乎意料的结果；
二、问题分析：
因为sort方法是v8实现的，所以第一反应就是v8的排序算法实现导致这个现象。
三、查看对应版本的v8源码
node 10版本的v8
通过 node -p process.versions.v8 可以查看v8的版本为：6.8.275.32-node.51
找到v8中Array.prototype.sort对应的代码，查看对应代码
这里不再展示代码详情，只对排序算法作说明：
- 首先，入口算法对长度小于10的，直接采用插入排序（原地执行）；
- 当长度大于10的时候，则采用快排，而主元的选择遵循以下规则：当数组长度大于1000，则选择第 200 - 225 中随机一位以及首、尾3个数，对这三个数原地排序后（比如选出 1, 4, 2，则排序成 1, 2, 4），选择中间的数（2）作为主元进行快排，数组长度小于1000时，则直接选择中间的数（去尾数取底，类似于 Math.floor）作为主元
- 当快排时切分的数组长度小于10的，则直接使用插入排序
接下来分析代码，看下为什么会出现如示例中的情况（下方代码省略了部分）
function QuickSort(a, from, to) {
var third_index = 0;
while (true) {
// Insertion sort is faster for short arrays.
if (to - from <= 10) {
InsertionSort(a, from, to);
return;
}
// 第一次进来时，to - from = 19
if (to - from > 1000) {
third_index = GetThirdIndex(a, from, to);
} else {
// 第一次取值为9
third_index = from + ((to - from) >> 1);
}
// Find a pivot as the median of first, last and middle element.
var v0 = a[from];
var v1 = a[to - 1];
var v2 = a[third_index];
// 对比取出的3个数，进行排序
// 因为comparefn返回永远是0，所以c01=0
var c01 = comparefn(v0, v1);
if (c01 > 0) {
// v1 < v0, so swap them.
var tmp = v0;
v0 = v1;
v1 = tmp;
} // v0 <= v1.
var c02 = comparefn(v0, v2);
// c02=0，所以交换了位置
if (c02 >= 0) {
// v2 <= v0 <= v1.
var tmp = v0;
v0 = v2;
v2 = v1;
v1 = tmp;
} else {
// v0 <= v1 && v0 < v2
var c12 = comparefn(v1, v2);
if (c12 > 0) {
// v0 <= v2 < v1
var tmp = v1;
v1 = v2;
v2 = tmp;
}
}
// v0 <= v1 <= v2
a[from] = v0;
a[to - 1] = v2;
var pivot = v1;
var low_end = from + 1; // Upper bound of elements lower than pivot.
var high_start = to - 1; // Lower bound of elements greater than pivot.
a[third_index] = a[low_end];
a[low_end] = pivot;
// .....more code
}
}
function GetThirdIndex(a, from, to) {
var t_array = new InternalArray();
// Use both 'from' and 'to' to determine the pivot candidates.
var increment = 200 + ((to - from) & 15);
var j = 0;
from += 1;
to -= 1;
for (var i = from; i < to; i += increment) {
t_array[j] = [i, a[i]];
j++;
}
t_array.sort(function(a, b) {
return comparefn(a[1], b[1]);
});
var third_index = t_array[t_array.length >> 1][0];
return third_index;
}
分析上面代码，可以发现示例中，位置错乱的原因发生在快排进行3数排序时，那么可以得出如下结论：
- 当待排序数组中，数组长度超过10个，并且存在排序优先级相同的多个元素，就可能出现排序不稳定的现象。
- 具体现象表现在排序后，打乱了原有数组的序，并且对用户来说相对不可预测。
而v8开发者针对这个现象的回复，则是：因为ES标准中，当sort方法的compare返回为0时，没有严格规定是否交换元素位置，而v8为了最大化排序的性能，使用的插入排序和变种快排的组合（时间复杂度：O(nlogn)、空间复杂度O(1)）的不稳定排序，导致了这个问题，在v8的issue 可以看到在这个问题的讨论过程。
那么对于应用开发者，我们则关注于怎么解决应用上的问题，当应用中已经大量使用了Array.prototype.sort方法的情况下，怎么快速修复？
下面提供一种通过覆盖原生sort方法修复的思路，有以下特点：
- 排序仍使用原生sort排序；
- 原生sort完之后，再将乱序的数组项按原数组的顺序排列，从而消除不稳定的问题；
- 优点：无需修改业务代码、时间复杂度与原来保持一致；
- 缺点：因引入一个保存索引的map，所以空间复杂度上升至O(n)；
const v8sort = Array.prototype.sort;
Array.prototype.sort = function(...args) {
if (this.length <2) {
return this;
}
const idxMap = this.reduce((acc, prev, idx) => {
acc.set(prev, idx);
return acc;
}, new Map());
v8sort.apply(this, args);
// 找出所有连续的等值子序列的起止位置
const subArray = [];
const [compareFn] = args;
let before = this[0];
let current;
let start = 0;
let end = 0;
for (let i = 1; i<this.length; i++) {
current = this[i];
if (compareFn(before, current) === 0) {
end += 1;
} else {
if (end > start) {
subArray.push([start, end]);
}
start = i;
end = i;
}
before = current;
}
if (end > start) {
subArray.push([start, end]);
}
const swap = (arr, a, b) => {
[arr[a], arr[b]] = [arr[b], arr[a]];
}
// 对等值子序列，根据原数组序进行插入排序
for (const [subStart, subEnd] of subArray) {
let j;
for (let i = subStart + 1; i <= subEnd; i++) {
j = i;
while (j > subStart && (idxMap.get(this[j]) <= idxMap.get(this[j-1]))) {
swap(this, j, j - 1);
j--;
}
}
}
}
node 12版本的v8
通过 node -p process.versions.v8 可以查看v8的版本为：7.8.279.23-node.31
该版本v8使用 Torque 的语言替代原来使用js实现的部分功能：
源码路径 /third_party/v8/builtins/array-sort.tq
新版本sort使用了稳定的TimSort排序算法，实现较为复杂，可以参考下面这张文章TimeSort实现
