第 173 题：讲下 V8 sort 的大概思路，并手写一个 sort 的实现-技术鸭(jishuya.cn)

在 V8 引擎中， 7.0 版本之前 ，数组长度小于 10 时， Array.prototype.sort() 使用的是插入排序，否则用快速排序。

在 V8 引擎 7.0 版本之后 就舍弃了快速排序，因为它不是稳定的排序算法，在最坏情况下，时间复杂度会降级到 O(n2)。

于是采用了一种混合排序的算法：TimSort 。

这种功能算法最初用于Python语言中，严格地说它不属于以上10种排序算法中的任何一种，属于一种混合排序算法：

在数据量小的子数组中使用插入排序，然后再使用归并排序将有序的子数组进行合并排序，时间复杂度为 O(nlogn) 。

什么是 TimSort ？

在解答 v8 sort 源码前，我们先看看 TimSort 具体是如何实现的，帮助我们阅读源码

Timsort 是 Tim Peter 在 2001 年为 Python 语言特意创造的，主要是基于现实数据集中存在者大量的有序元素（不需要重新排序）。Timsort 会遍历所有数据，找出数据中所有有序的分区（run），然后按照一定的规则将这些分区（run）归并为一个。

具体过程为：

扫描数组，并寻找所谓的 _runs_ ，一个 run 可以认为是已经排序的小数组，也包括以逆向排序的，因为这些数组可以简单地翻转（reverse）就成为一个run
确定最小 run 长度，小于的 run 会通过 插入排序 归并成长度高于最小长度的 run
反复归并一些相邻 run ，过程中避免归并长度相差很大的片段，直至整个排序完成

实现：

// 顺序合并两个小数组left、right 到 result
function merge(left, right) {
  let result = [],
      ileft = 0,
      iright = 0
  while(ileft < left.length && iright < right.length) {
    if(left[ileft] < right[iright]){
      result.push(left[ileft ++])
    } else {
      result.push(right[iright ++])
    }
  }
  while(ileft < left.length) {
    result.push(left[ileft ++])
  }
  while(iright < right.length) {
    result.push(right[iright ++])
  }
  return result
}
 
// 插入排序
function insertionSort(arr) {
    let n = arr.length;
    let preIndex, current;
    for (let i = 1; i < n; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}
 
// timsort
function timsort(arr) {
    // 空数组或数组长度小于 2，直接返回
    if(!arr || arr.length < 2) return arr
    let runs = [], 
        sortedRuns = [],
        newRun = [arr[0]],
        length = arr.length
    // 划分 run 区，并存储到 runs 中，这里简单的按照升序划分，没有考虑降序的run
    for(let i = 1; i < length; i++) {
        if(arr[i] < arr[i - 1]) {
            runs.push(newRun)
            newRun = [arr[i]]
        } else {
            newRun.push(arr[i])
        }
        if(length - 1 === i) {
            runs.push(newRun)
            break
        }
    }
    // 由于仅仅是升序的run，没有涉及到run的扩充和降序的run，因此，其实这里没有必要使用 insertionSort 来进行 run 自身的排序
    for(let run of runs) {
        insertionSort(run)
    }
    // 合并 runs
    sortedRuns = []
    for(let run of runs) {
        sortedRuns = merge(sortedRuns, run)
    }
    return sortedRuns
}
 
// 测试
var numbers = [4, 2, 5, 1, 3]
timsort(numbers)
// [1, 2, 3, 4, 5]

源码：v8/array-sort.tq at master · v8/v8 · GitHub

即 TimSort 在 v8 中的实现，具体实现步骤如下：

判断数组长度，小于2直接返回，不排序
开始循环
找出一个有序子数组，我们称之为 run ，长度 currentRunLength
计算最小合并序列长度 minRunLength （这个值会根据数组长度动态变化，在32~64之间）
比较 currentRunLength 和 minRunLength ，如果 currentRunLength >= minRunLength ，否则采用插入排序补足数组长度至 minRunLength ，将 run 压入栈 pendingRuns 中
每次有新的 run 被压入 pendingRuns 时保证栈内任意 3 个连续的 run（run0, run1, run2）从下至上满足run0 > run1 + run2 && run1 > run2 ，不满足的话进行调整直至满足
如果剩余子数组为 0 ，结束循环
合并栈中所有 run，排序结束

总的来说，此算法将数组看成若干有序子数组，利用归并排序算法合并这些有序数组。为了缩小归并排序时间，通过插入排序的方式将这些子数组整理为arr1.length>arr2.length+arr3.length,且arr2.length>arr3.length

文章版权归作者所有，未经允许请勿转载。

THE END