爱囡囡，爱前端

0%

Array.prototype.sort的排序原理

发表于 分类于 ， ，

最近一直在更新 Typescript 数据结构与算法系列，在学习中对 JS 的 sort 方法产生了好奇，Array.prototype.sort()的用法肯定都比较熟悉：

1
arr.sort([compareFunction]);

sort 方法的参数为一个可选的排序回调函数 compareFunction，回调函数中有两个用于比较的参数。如果省略，元素按照转换为的字符串的各个字符的 Unicode 位点进行排序。整个 sort 方法会返回排序后的数组，但是原数组已经原地排序。

但是这个 Array.prototype.sort() 的逻辑是什么，用到的排序方法是什么，时间和空间复杂度是多少都不清楚，本篇从 ECMA262 标准，V8 引擎源码来探究 sort 方法。

ECMA262

既然要排序，肯定会用的到大小比较，在 ECMA262 中对大小的关系的定义翻译如下：

大小关系比较原文

比较 x < y（其中 x 和 y 是值）会产生 true``，false 或 undefined（表示有至少一个操作数是 NaN）。除 x 和 y 外，该算法还使用名为 LeftFirst 的布尔标志作为参数。该标志用于控制对 x 和 y 执行具有潜在副作用的操作的顺序。这是必需的，因为 ECMAScript 指定了表达式的从左到右计算。 LeftFirst 的默认值为 true ，表示先在 x 参数位置计算表达式。如果 LeftFirst 为 false，则情况相反，必须现在 y 上执行操作。比较执行如下：

  1. 如果 LeftFirst 标志为 true, 则
    1. 让 px 为 ?ToPrimitive(x, number).
    2. 让 py 为 ?ToPrimitive(y, number).
  2. 否则,
    1. 让 py 为 ?ToPrimitive(y, number).
    2. 让 px 为 ?ToPrimitive(x, number).
  3. 如果 Type(px) 为 String 并且 Type(py) 为 String, 则
    1. 如果 IsStringPrefix(py, px) 为 true, 返回 false.
    2. 如果 IsStringPrefix(px, py) 为 true, 返回 true.
    3. 令 k 为最小的非负整数，这个非负整数能使 px 上 k 索引处的代码单元与 py 上 k 索引处的代码单元不同。
    4. 让 m 为 px 上 k 索引处的代码单元整数值.
    5. 让 n 为 py 上 k 索引处的代码单元整数值.
    6. 如果 m < n, 返回 true. 否则, 返回 false.
  4. 否则,
    1. 如果 Type(px) 为 BigInt 并且 Type(py) 为 String, 则
      1. 让 ny 为 !StringToBigInt(py).
      2. 如果 ny 为 NaN, 返回 undefined.
      3. 返回 BigInt::lessThan(px, ny).
    2. 如果 Type(px) 为 String 并且 Type(py) 为 BigInt, 则
      1. 让 nx 为 !StringToBigInt(px).
      2. 如果 nx 为 NaN, 返回 undefined.
      3. 返回 BigInt::lessThan(nx, py).
    3. 让 nx 为 !ToNumeric(px).
    4. 让 ny 为 !ToNumeric(py).
    5. 如果 Type(nx) 与 Type(ny) 相同, 返回 Type(nx)::lessThan(nx, ny).
    6. 断言: Type(nx) 为 BigInt 并且 Type(ny) 为 Number, 或 Type(nx) 为 Number 并且 Type(ny) 为 BigInt.
    7. 如果 nx 或 ny 为 NaN, 返回 undefined.
    8. 如果 nx 为 -∞𝔽 或 ny 为 +∞𝔽, 返回 true.
    9. 如果 nx 为 +∞𝔽 或 ny 为 -∞𝔽, 返回 false.
    10. 如果 ℝ(nx) < ℝ(ny), 返回 true; 否则返回 false.

注意：字符串的比较使用的是简单的代码单元值的字典顺序。没有尝试使用 Unicode 规范中定义的更复杂的，面向语义的字符或字符串相等性定义以及整理顺序。因此，根据 Unicode 标准规范 相等 的字符串值可能会被测试为 不相等。实际上，该算法假定两个字符串都已经处于规范化形式。另外请注意，对于包含补充字符的字符串，UTF-16 代码单元值序列的字典顺序与代码点值序列的字典顺序不同。

大小关系比较总结

将 x < y 上面的步骤进行下简单总结：

  1. 如果 x 和 y 都为 String 类型，则
    1. 如果 x 是 y 或 y 是 x 的前缀，则短的这个小
    2. 否则比较 x 和 y 的 代码单元 值的大小
  2. 否则 x 和 y 都转化为数字类型后再比较大小，如果转换过程中出现了 NaN，就返回 undefined（但其实在其他章节中提到过，要将 undefined 变为 false）

注意：JS 的编码格式为 UTF-16，所以用 16 位二进制来表示所有的字符，当代码点过大时，比如部分汉字和各种 emoji 表情文字，就需要 2 个 16 位二进制来表示，也就是用 2 个代码单元来表示。（具体学习可见阮老师的博客）。

理解了 ECMA262 给出的标准，就能理解下述代码中的大小关系比较了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 字符串之间 先比较前缀
 */
'lin' < 'linjingyi'; // x 是 y 的前缀，则为 true （3.2）
'linjingyi' < 'lin'; // y 是 x 的前缀，则为 false （3.1）

/**
 * 字符串之间 再比较代码单元
 */
'm' < 'n'; // 代码单元值， 006d < 006e 为 true （3.6，k 为 0）
'm' < 'l'; // 代码单元值， 006d < 006c 为 false （3.6， k 为 0）
'你' < '我'; // 代码单元值， 4f60 < 6211 为 true （3.6， k 为 0）
'ml' < 'mn'; // 代码单元值，006d 006c < 006d 006e 为 true （3.6，k 为 1）
'你好' < '我好'; // 代码单元值，4f60 597d < 6211 597d 为 true （3.6，k 为 1）
'你好' < '我'; // 代码单元值，4f60 597d < 6211 为 true （3.6，k 为 1）
'10' < '2'; // 这也是字符串比较，所以也是代码单元值比较，0031 0030 < 0032 为 true （3.6，k 为 0）
'🍎' < '😙'; // emoji 文字，仍然为字符串，代码点太大，所以由两个代码单元组成 d83c df4e < d83d de19 为 true（3.6，k 为 0）
'😍' < '😙'; // 同理比较代码单元值 d83d de0d < d83d de19 为 true（3.6，k 为 1）

/**
 * 字符串和数字比较 先进行类型转换
 */
'10' < 2; // 10转为数字10，10 < 2 为 false （4.1.3）
'm' < 2 // m 转为数字 NaN， NaN < 2 为 false （4.1.2）


/**
 * 其他类型互相比较(包括其他类型和数字比较) 先进行类型转换
 * undefined -> NaN
 * null -> 0
 * true -> 1
 * false -> 0
 * String -> 对应数字或者NaN
 * Object -> 调用 toString 转为 String -> 对应数字或者NaN
 */
null < 1 // 0 < 1，true（4.5）
false < 1 // 0 < 1，true（4.5）
undefined < 1 // NaN < 1，false（4.7）
true < 2 // 1 < 2, true（4.5）
true < '2' // 1 < 2， true（4.5）
null < true // 0 < 1，true（4.5）
({}) < ([]) // '[object Object]' < ''，false（4.5）
({}) < ([1，2，3]) // '[object Object]' < '1，2，3'，false（4.5）
({}) < (['你好'，2，3]) // '[object Object]' < '你好，2，3' 等价于 '[' < '你' 等价于 005b < 4f60，true（4.5）

理解了大小比较的原理，可以继续向下推进了。在 ECMA262 标准中也找到了 Array.prototype.sort() 部分，下面我把继续它翻译一下，大部分内容都比较学术，对原文不感兴趣可以跳到重点分析部分：

Array.prototype.sort(comparefn)

排序数组中的元素。排序必须稳定（也就是说，相等的元素必须保持其原始先后顺序）。如果 comparefn 不是 undefined ，则它应该是一个接受两个参数 x 和 y 的函数，如果 x < y 该函数返回负数，如果 x > y 则返回正数，否则返回 0。

当调用 sort 方法时，将执行以下步骤：

  1. 如果 comparefn 不为 undefined ，并且 IsCallable(comparefn) 返回 false, 抛出 TypeError 错误.
  2. 让 obj 为 ?ToObject(this value).
  3. 让 len 为 ?LengthOfArrayLike(obj).
  4. 让 items 为新的空 List.
  5. 让 k 为 0.
  6. 循环, while k < len,
    1. 让 Pk 为 !ToString(𝔽(k)).
    2. 让 kPresent 为 ?HasProperty(obj, Pk).
    3. 如果 kPresent 为 true, 则
      1. 让 kValue 为 ?Get(obj, Pk).
      2. 添加 kValue 到 items 中.
    4. 设 k 为 k + 1.
  7. 让 itemCount 为 items 的元素数目.
  8. 由具体 引擎实现自己决定 的排序方法并调用 SortCompare 来对 items 进行排序。如果调用返回了一个 异常完成，则停止进一步调用 SortCompare 或停止算法中的后续步骤，然后返回该完成。
  9. 让 j 为 0.
  10. 循环, while j < itemCount,
    1. 执行 ?Set(obj, !ToString(𝔽(j)), items[j], true).
    2. 设 j 为 j + 1.
  11. 循环, while j < len,
    1. 执行 ?DeletePropertyOrThrow(obj, !ToString(𝔽(j))).
    2. 设 j 为 j + 1.
  12. 返回 obj.

排序顺序是指排序完成后，对 整数索引 小于 len 的 obj 属性值的先后顺序。sort 函数的结果由以下方式确定：

如果下述任何条件为真，则排序顺序由具体引擎实现自己决定：

  • 如果 comparefn 不为 undefined，并且对 items 元素不是一致比较函数（参见下文）。

  • 如果 comparefn 为 undefined，并且 SortCompare 不是一致比较函数。

  • 如果 comparefn 为 undefined，并且 ToString 的所有应用（传递任意特定值参数给 SortCompare ），不会产生相同的结果。

除非以上将排序顺序指定为引擎实现自己决定，否则在执行上述算法的步骤 8 之后，items 必须满足以下所有条件：

  • 必须存在一些小于 itemCount 的非负整数组成的数学排列 π，在排列中，对于每个小于 itemCount 的非负整数 j，元素 old[j] 与 new[π(j)] 相同。
  • 然后，对于所有的小于 itemCount 的非负整数 j and k, 如果 SortCompare(old[j], old[k]) < 0, 则 π(j) < π(k).

这里的 old[j] 是指执行步骤 8 之前的 items[j]，而 new[j] 是指是指执行步骤 8 之后的 items[j]。

comparefn 函数是一个一致比较函数，一致比较的定义如下：

规定 a, b 和 c 都是集合 s 中的值（值可能相等），a <CF b 表示 comparefn(a, b) < 0; a =CF b 表示 comparefn(a, b) = 0; a >CF b 表示 comparefn(a, b) > 0。

  • 传参一对特定的值 a 和 b 来调用 comparefn(a, b) 始终返回相同的值 v。此外, Type(v) 为 Number, 并且 v 不为 NaN。 注意，这也意味着对于给定一对值a 和 b，条件a <CF b, a =CF b 和 a >CF b 中必有且只有一个为真。
  • 调用 comparefn(a, b) 不会修改 obj 或 obj 原型链上的任何对象.
  • a =CF a (自反性)
  • 如果 a =CF b, 则 b =CF a (对称性)
  • 如果 a =CF b 且 b =CF c, 则 a =CF c (=CF 的传递性)
  • 如果 a <CF b 且 b <CF c, 则 a <CF c (<CF 的传递性)
  • 如果 a >CF b 且 b >CF c, 则 a >CF c (>CF 的传递性)

NOTE 1
以上条件的充分必要条件是 comparefn 将集合 S 划分为等价类并且确保这些等价类完全有序。

NOTE 2
sort 函数是故意泛型的；它不需要它的 this 值是一个 Array 对象。因此，可以将其作为一个方法转移到其他类型的对象中。

SortCompare(x, y)

抽象操作 SortCompare 接受参数 x 和 y。它也可以访问 sort 方法当前调用的 comparefn 参数。调用时，它将执行以下步骤：

  1. 如果 x 和 y 都为 undefined, 返回 +0𝔽.
  2. 如果 x 为 undefined, 返回 1𝔽.
  3. 如果 y 为 undefined, 返回 -1𝔽.
  4. 如果 comparefn 不为 undefined, 则
    1. 让 v 为 ?ToNumber(?Call(comparefn, undefined, « x, y »)).
    2. 如果 v 为 NaN, 返回 +0𝔽.
    3. 返回 v.
  5. 让 xString 为 ?ToString(x).
  6. 让 yString 为 ?ToString(y).
  7. 让 xSmaller 为执行 Abstract Relational Comparison xString < yString的结果.
  8. 如果 xSmaller 为 true, 返回 -1𝔽.
  9. 让 ySmaller 为执行 Abstract Relational Comparison yString < xString的结果.
  10. 如果 ySmaller 为 true, 返回 1𝔽.
  11. 返回 +0𝔽.

NOTE 1
因为不存在的属性值总是大于 undefined 属性值，而 undefined 总是大于任何其他值，所以 undefined 属性值在排序时总是在结果的末尾，接下来是是不存在的属性值。

NOTE 2
由步骤 5 和 6 中的 ToString 抽象操作 执行的方法调用有可能导致 SortCompare 不能表现为 一致比较函数。

sort 规范 总结

ECMA262 的相关规范的原文很复杂，但是两节整体来讲，可以突出这么几个重点：

先分析SortCompare(x, y)，假设比较的第一个参数为 x，比较的第二个参数为 y：

  • 如果只有 x 为 undefined，返回 1；如果只有 y 为 undefined，返回 -1；如果都为 undefined，返回 +0（根本不会执行回调函数 comparefn）
  • 如果传入了回调函数 comparefn，则执行回调函数并数字化后返回（如果为 NaN 返回 +0）
  • 如果没传回调函数 comparefn，就把 x 和 y 字符串化，然后执行字符串间的 大小关系比较，如果 x 小返回 1，如果 y 小返回 -1，相等返回 +0

再分析 Array.prototype.sort(comparefn) 的原文，可以发现：

  • sort 会修改原数组
  • sort 要返回修改后的数组
  • sort 排序算法的选择是 JS 引擎自己决定的
  • sort 函数是泛型的，可以用到别的类数组对象中
  • comparefn 得是个一致比较函数，具备自反性，对称性和传递性

所以综合起来看，也会得到另外一个结论：如果被比较的值为 undefined，根本不会执行比较操作就会返回单次比较结果，而且排序完成后所有的 undefined 放在最后。

V8 引擎实现

既然 ECMA262 规定了引擎在实现 sort 的排序算法时可以自己选择，现在就深入源码，看看使用量最大的 V8 怎么实现的。

V8 引擎是现在改为了谷歌自研的 tq 语言来实现，sort 的实现页足足有 1400 行，实现的核心算法是 timsort 排序方法。看的头疼，翻译一篇国外文章 Tim sort, the fastest sort used in v8 and Python

Tim sort, the fastest sort used in v8 and Python

Tim Sort 是在 2002 年由 Python 的主要贡献者之一 Tim Peters 为改进 Python list 排序性能而创建的，是通过对现实世界数据的分析来实现的一种算法组合。最好时间复杂度为 O(n)，最坏时间复杂度为 O(nlogn)，比快排的最坏时间复杂度 O(n²) 优秀的多。

二分插入排序和归并排序

在实现的时候，如果数据量较小使用二分插入排序，下图是插入排序和二分插入排序：

当数据量较大时，就会使用归并排序的思想，将长 list 分解为更小的 runs，然后统一合并，如下图：

分割为 runs

传统归并算法中，常将 2 个数据分为一组 run 。但 Tim 实验发现，适当提高 run 的初始大小会有明显的性能提升，但每组也不能太大，将分组定为 32～64 左右比较合适。

与此同时，他还发现在现实世界的数据中，有许多数据片段是按升序或降序排序的，不需要额外排序。因此他决定以一个“自然”的大小来划分 run —— 初始 runs 的大小不是一个固定的数字，而是一个最小的长度要求 —— “min run”。

以下是划分的准则:

  1. 通过比较前两个 item 设置一个 descending flag，如果只有一个 item，则设置为 false。
  2. 循环剩下的 items，并检查它们是否仍然以升序 或 严格降序 排列，直到反转。
  3. 现在有了一个 升序 或 严格降序 排列的 run。如果 run 是严格降序，则反转它。严格 的原因是为了保持算法的稳定性。
  4. 然后检查这个 run 的长度是否满足“min run”的要求。如果不满足，则补偿剩下的 items 以达到最小长度，并从补偿项开始执行二分插入排序。

下面是 js 实现的伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
let nremaining = list.length;
const runs = [];
const minrun = merge_compute_minrun(nremaining);

function count_run(list) {
  let descending = false;
  let n = 1;

  if (list.length === 1) return n;
  if (list[n] < list[n - 1]) {
    descending = true;
  }
  n++;
  while (n < list.length && (list[n] < list[n - 1] || !desending)) {
    n++;
  }
  return {
    size: n,
    descending,
  };
}

do {
  const startIndex = list.length - nremaining;
  let { size, descending } = count_run();
  if (descending)
    reverse(
      list,
      // start index
      startIndex,
      // length to revert
      size
    );
  if (n < minrun) {
    const force = nremaining <= minrun ? nremaining : minrun;
    binarysort(
      list,
      // sort start index
      startIndex,
      // sort length
      force,
      // index to start binary search
      list.length - nremaining + size
    );
    size = force;
  }
  nremaining -= n;
  runs.push({ startIndex, size });
} while (nremaining);

为了使归并操作更加平衡，最好有 2的幂次方 个 runs。因此 Tim 将总长度不断除以 2，直到这个值小于 64，并向上或向下取整得出 min run:

1
2
3
4
5
6
7
8
function merge_compute_minrun(n) {
  var r = 0; /* becomes 1 if any 1 bits are shifted off */
  while (n >= 64) {
    r |= n & 1;
    n >>= 1;
  }
  return n + r;
}

平衡归并

经典的归并排序只是简单地将相邻的 2 个 runs 合并。因为需要挨个比较两个有序数组中的元素的大小，然后将合并后的 list 存储在内存中，所以它将占用相当多的内存空间。Tim 发现有一些方法可以处理这种不必要的内存浪费。

为了达成目标，需要解决的第一个问题是以下哪两个 runs 合并性能最优？

假设有 3 个 runs:

  • A: 1000 个元素
  • B: 2000 个元素
  • C: 1000 个元素

很显然先合并 A 和 C 将更加平衡。但是存在一个问题，如果 A、 B 、C 中都存在一个相同元素，那么首先将 A 和 C 合并，再去和 B 合并时将改变该元素的顺序并影响算法稳定性。

因此，Tim sort 仍然只合并相邻的 2 个 runs，但是用了更精巧的一种方式：

比较 3 个相邻 runs 的长度。如果它们满足以下规则:

1
2
A > B + C
B > C

也就意味着 B 和 C 是相对较小的 runs。所以首先合并较小的 runs，然后就与 A 的长度更接近了，再继续合并。

经过上述操作之后，如果仍然剩了一些 runs，那么就按正常的顺序来合并。

使用 gallop 模式归并

当尝试合并大型 runs 时，因为他们都是有序的，所以很可能很久才能找到正确的放置位置。例如:

  • A: [0, 2, 4, 6, 8, 10, …, 100]
  • B: [57, 77, 97, …]

就拿 B - 57 与 A - 0 进行比较，57 将比较 58/2 = 29 次来找到正确的位置。然后下一个 B - 77，需要再比较 (78-58)/2 = 10 次。

不仅比较本身毫无意义，还会额外浪费很大的内存空间。因此，Tim sort 使用 gallop 来加速这个过程。与二分搜索相比，虽然复杂度是相同的，但是 gallop 更擅长寻找距离开始搜索位置不远的数据。

它首先选择一个位置（不一定是首或尾位置）开始搜索，然后根据起始元素与目标数据的大小比较来选择搜索方向。如果一次搜索失败，下一次它将通过乘 2 来尝试更远的位置。

例如，如果从 A[7] 开始搜索，而 A[7] 比目标数据小，那么下一步比较 A[9] ，然后是 A[11] ，A[15] ，A[23] ，A[35] … 直到发现一个大于等于目标数据的元素。假设 A[35] 较大 ，那么就知道目标数据肯定位于 A[23] 和 A[35] 之间的某个位置。

一旦得到这个粗略的范围，然后就切换到二分搜索，找到精确的位置。

下面是伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
function gallop_left(
  key, // the data to merge
  a, // the run to merge to
  startIndex
) {
  let lastofs = 0; // starting point for binary search
  let ofs = 1; // end point for binary search
  const n = a.length;
  if (a[hint] < key) {
    // compare from left to right
    const maxofs = n - hint;
    while (ofs < maxofs && a[ofs] < key) {
      lastofs = ofs;
      ofs = (ofs << 1) + 1;
    }
    if (ofs > maxofs) ofs = maxofs;
    lastofs += hint;
    ofs += hint;
  } else {
    // compare from right to left
    const maxofs = hint + 1;
    while (ofs < maxofs && a[hint - ofs] < key) {
      lastofs = ofs;
      ofs = (ofs << 1) + 1;
    }
    if (ofs > maxofs) ofs = maxofs;
    let tmp = lastofs;
    lastofs = hint - ofs;
    ofs = hint - tmp;
  }

  // do binary search at the end
  ++lastofs;
  while (lastofs < ofs) {
    let m = lastofs + ((ofs - lastofs) >> 1);
    if (a[m] < key) lastofs = m + 1;
    else ofs = m;
  }
  return ofs; // return the found index
}

何时使用 gallop 模式

刚开始合并时，两个 runs 之间可能会有很大的间隔。例如仍然是下面两个数组:

  • A: [0, 2, 4, 6, 8, 10, …, 100]
  • B: [57, 77, 97, …]

所以在这里可以使用 gallop_left(b[0], a, 0)（从左侧某位置开始），来快速定位 B[0] 应该在 A 中的位置；然后使用 gallop_right(a[a.length - 1], b, b.length - 1)（从右侧某位置开始），来定位 A[0] 应该在 B 中的位置。这样就可以缩短所需比较数据的大小，后再真正需要进行比较和合并。

gallop_left 和 gallop_right 的实现基本一致，只是对边界情况有一些不同的处理。

下面是伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function merge(ms /* MergeState */, a, b) {
  let k = gallop_right(b[0], a, 0);
  if (k < 0) throw -1;
  let merged = a.splice(0, k);
  if (a.length == 0) return merged.concat(b);
  else merged.push(b.shift());

  let nb = gallop_left(a[a.length - 1], b, b.length - 1);
  if (nb <= 0) throw nb;
  const lastPart = b.splice(nb);
  lastPart.unshift(a.pop());

  if (a.length <= nb) merged = merged.concat(merge_lo(ms, a, b));
  else merged = merged.concat(merge_hi(ms, a, b));
  return merged.concat(lastPart);
}

Gallop 模式很棒，但只有在 runs 的长度存在较大差距时才高效，否则只会降低性能。因此 Tim sort 引入了一些使用 Gallop 模式 的规则。

在 Python 中，只有当一个数据比较 7 次但仍然没有找到它应该放置的位置时，才会进入 Gallop 模式。更有趣的事情是，如果发现合并 runs 之后继续进入了 Gallop 模式，“7 次” 这个约束条件将变小。如果没有触发 Gallop 模式，那么就重置一下约束条件。

下面是伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
const MIN_GALLOP = 7;

function merge_lo(
  ms, // MergeState
  a, // the shorter run
  b // the longer run
) {
      let min_gallop = ms.min_gallop;
    let merged = [];

    for (;;) {
        let acount = 0;          /* # of times A won in a row */
        let bcount = 0;          /* # of times B won in a row */

        // do sequential comparing first, util it fulfils the galloping constrain
        do {
            if (b[0] < a[0]) {
                merged.push(b.shift());
                ++bcount;
                acount = 0;
                if (b.length == 0) return merged.concat(a);
            } else {
                merged.push(a.shift());
                ++acount;
                bcount = 0;
                if (a.length == 0) return merged.concat(b);
            }
        } while ((acount || bcount) >= min_gallop))

        // galloping and merging
        ++min_gallop;
        do {
            ms.min_gallop = min_gallop -= min_gallop > 1;
            let k = gallop_right(b[0], a, 0);
            acount = k;
            if (k) {
                if (k < 0) return -1;
                merged = merged.concat(a.splice(0, k));
                if (a.length == 0) return merged.concat(b);
            }
            merged.push(b.shift());
            if (b.length == 0) return merged.concat(a);

            k = gallop_left(a[0], b, 0);
            bcount = k;
            if (k) {
                if (k < 0) return -1;
                merged = merged.concat(b.splice(0, k));
                if (b.length == 0) return merged.concat(a);
            }
              merged.push(a.shift());
            if (a.length == 0) return merged.concat(b);
        } while (acount >= MIN_GALLOP || bcount >= MIN_GALLOP);
        ms.min_gallop = ++min_gallop;
    }
    return merged;
 }

实际上还有一个函数叫做 merge_hi。因为与 merge_lo 非常相似，所以跳过它。

总结

从 ECMA262 关于 sort 的规定 到 大小关系比较 的原理，再到 V8 引擎实现原理，从头到尾梳理了一遍 Array.prototype.sort ，可以回答开头的几个问题：

  1. ECMA262 规范中 Array.prototype.sort 的逻辑是什么？
    先定义一个大小比较的标准 SortCompare，这个 SortCompare 要具有自反性，对称性和传递性；再定义 sort 需要修改原数组并返回修改后的数组；最后定义由引擎开发者自己决定用什么排序算法来实现。
  2. Array.prototype.sort 排序方法是什么？
    不是常见的排序算法中的任何一种，而是学习了 python 的排序实现，使用了 Tim 实现的 Tim sort 算法，汇集了各种优化。
  3. 复杂度是多少？
    最好时间复杂度为 O(n)，平均时间复杂度 O(nlogn)，最坏时间复杂度为 O(nlogn)，比最常用的快速排序的最坏时间复杂度 O(n²) 要更优秀；空间复杂度为 O(n)，并且为稳定排序算法。

前端记事本，不定期更新，欢迎关注！

👆 全文结束，棒槌时间到 👇