一个Bug引发的V8排序算法学习总结

零、简述：

最近在工作中，发现一个排序错乱的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实现