通过V8源码看一个关于JS数组排序的诡异问题

前言

前几天一个朋友在微信里面问我一个关于 JS 数组排序的问题。通过该问题发现了一些之前没发现的内容，下面话不多少了，来一起看看详细的介绍吧。

原始数组如下：

var data = [ {value: 4},  {value: 2},  {value: undefined},  {value: undefined},  {value: 1},  {value: undefined},  {value: undefined},  {value: 7},  {value: undefined},  {value: 4}];

data 是个数组，数组的每一项都是一个拥有 value 作为 key 的对象，值为数字或者 undefined。

data .sort((x, y) => x.value - y.value) .map(x => x.value);

对数组的 value 进行排序，然后把排完序的数组进行 flat 处理。得到的结果如下：

[2, 4, undefined, undefined, 1, undefined, undefined, 7, undefined, 4]

显然这没有达到我们的目的。

现在我们修改一下排序，挑战一下函数的调用顺序：先对数组进行扁平化(flat)处理，然后再排序。

data .map(x => x.value) .sort((x, y) => x - y)

这时我们得到的结果和之前截然不同：

[1, 2, 4, 4, 7, undefined, undefined, undefined, undefined, undefined]

遇到这种情况第一感觉肯定是要去看看 ECMA 规范，万一是 JS 引擎的 bug 呢。

在 ES6 规范 22.1.3.24 节写道：

Calling comparefn(a,b) always returns the same value v when given a specific pair of values a and b as its two arguments. Furthermore, Type(v) is Number, and v is not NaN. Note that this implies that exactly one of a < b, a = b, and a > b will be true for a given pair of a and b.

简单翻译一下就是：第二个参数 comparefn 返回一个数字，并且不是 NaN。一个注意事项是，对于参与比较的两个数 a 小于 b、a 等于 b、a 大于 b 这三种情况必须有一个为 true。

所以严格意义上来说，这段代码是有 bug 的，因为比较的结果出现了 NaN。

在 MDN 文档上还有一个细节：

如果 comparefn(a, b) 等于 0， a 和 b 的相对位置不变。备注：ECMAScript 标准并不保证这一行为，而且也不是所有浏览器都会遵守。

翻译成编程术语就是：sort 排序算法是不稳定排序。

其实我们最疑惑的问题上，上面两行代码为什么会输出不同的结果。我们只能通过查看 V8 源码去找答案了。

V8 对数组排序是这样进行的：

如果没有定义 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;};

然后定义了一个插入排序算法：