一.背景

在JS中排序很难。本文致力于发现排序算法和JS交互之间的怪癖，并讲述将V8迁移到稳定算法和可预测性能的过程。

当比较不同的排序算法时，我们会用描述内存操作或比较次数渐进增长的“大O表示法”，去比较最差性能和平均性能。

你需要知道，在动态语言（如 JS）中，一次比较操作付出的代价远高于一次内存访问。

这是因为在排序时比较两个值，通常意味着调用开发者的代码。

让我们看一个简单的升序排序函数。当两个比较的值结果是小于、等于、大于时，比较函数应对应返回负数、0、正数。

不遵循上述模式的比较函数，其可能会产生副作用，比如修改要排序的数组。

const array = [4, 2, 5, 3, 1];

function compare(a, b) {

// Arbitrary code goes here, e.g. `array.push(1);`.

return a - b;

// A “typical” sort call.

array.sort(compare);

再来一个示例，也可能调用开发者的代码。因为默认的比较函数是调用toString进行字典比较。

const array = [4, 2, 5, 3, 1];

array.push({

toString() {

// Arbitrary code goes here, e.g. `array.push(1);`.

return '42';

});

// Sort without a comparison function.

array.sort();

感兴趣的同学，可以自行阅读 V8 sort test 测试用例

二.极端情况：访问器和原型链交互

在本节我们将离开规范，进入“实现定义”的具体部分。

排序规范有一个完整的条件列表，当满足这些条件时，引擎将采用它认为合适的方式，对对象/数组进行排序，或者根本不排序。

引擎一定会遵循一些基本的规范，除此之外的规则会发生什么，只有引擎自己知道。比如 访问器和原型链交互。

一方面，这给了引擎开发人员自由去尝试不同的实现；另一方面，对于规范未定义的行为，JS开发者也期望出现符合预期的“合理行为”。

实际上，“合理行为”很难去界定。所以，引擎不会针对这种代码进行优化。

在Array#sort的某些极端情况，引擎行为仍存在很大差异。

第一个示例，一个包含访问器（即getter和setter）的数组，以及该代码在不同JS引擎中的执行情况。

const array = [0, 1, 2];

Object.defineProperty(array, '0', {

get() { console.log('get 0'); return 0; },

set(v) { console.log('set 0'); }

});

Object.defineProperty(array, '1', {

get() { console.log('get 1'); return 1; },

set(v) { console.log('set 1'); }

});

array.sort();

该代码在各种JS引擎中的输出如下。

这里没有绝对正确和错误的答案，因为这是规范留白给引擎去实现的。

// Chakra: 微软从IE9开始推出的新JavaScript引擎

get 0

get 1

set 0

set 1

// JavaScriptCore: C++实现的开源项目, 是WebKit的一部分