有没有人知道v8在实现排序的时候为什么对小数组用插入排序？

Question

https://github.com/v8/v8/blob...

// Insertion sort is faster for short arrays.

这个原因是v8对此有优化还是这个算法本身是这样呢，我所知道就是quickSort应该要比InsertionSort快

我写了以下代码比较，但是10个以下的排序实在是太快了，看不到有区别

void function(){
      var comparefn = function (x, y) {
            if (x === y) return 0;
            else return x < y ? -1 : 1;
          };

        var InsertionSort = function InsertionSort(a, from, to) {
          for (var i = from + 1; i < to; i++) {
            var element = a[i];
            for (var j = i - 1; j >= from; j--) {
              var tmp = a[j];
              var order = comparefn(tmp, element);
              if (order > 0) {
                a[j + 1] = tmp;
              } else {
                break;
              }
            }
            a[j + 1] = element;
          }
        };  

        var QuickSort = function QuickSort(a, from, to) {
          var third_index = 0;
          while (true) {
            if (to - from <= 1) {
              return;
            }
            // 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];
            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);
            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;

            // From low_end to i are elements equal to pivot.
            // From i to high_start are elements that haven't been compared yet.
            partition: for (var i = low_end + 1; i < high_start; i++) {
              var element = a[i];
              var order = comparefn(element, pivot);
              if (order < 0) {
                a[i] = a[low_end];
                a[low_end] = element;
                low_end++;
              } else if (order > 0) {
                do {
                  high_start--;
                  if (high_start == i) break partition;
                  var top_elem = a[high_start];
                  order = comparefn(top_elem, pivot);
                } while (order > 0);
                a[i] = a[high_start];
                a[high_start] = element;
                if (order < 0) {
                  element = a[i];
                  a[i] = a[low_end];
                  a[low_end] = element;
                  low_end++;
                }
              }
            }
            if (to - high_start < low_end - from) {
              QuickSort(a, high_start, to);
              to = low_end;
            } else {
              QuickSort(a, from, low_end);
              from = high_start;
            }
          }
        };

    let iArr = [],qArr = [];
    for(let ii=0;ii<5000;ii++){

      let arr1 = function () {
        let r = [];
        for (let i = 0; i < 10; i++) {
          r.push(10 + Math.round(Math.random() * 100));
        }
        return r;
      } ()

      let arr2 = arr1.slice();

//       let arr3 = function () {
//         let r = [];
//         for (let i = 0; i < 500; i++) {
//           r.push(10 + Math.round(Math.random() * 100));
//         }
//         return r;
//       } ()

//       let arr4 = arr3.slice();

      var t = Date.now();
      InsertionSort(arr1,0,arr1.length -1);
      iArr.push(Date.now() - t);

      t = Date.now();
      QuickSort(arr2,0,arr2.length -1);
      qArr.push(Date.now() - t);

    }

    console.log(iArr.reduce((a,b)=>a+b));
    console.log(qArr.reduce((a,b)=>a+b));


//       t = Date.now();
//       InsertionSort(arr3,0,arr3.length -1);
//       console.log(`500 arr InsertionSort ${ Date.now() - t}`)

//       t = Date.now();
//       QuickSort(arr4,0,arr4.length -1);
//       console.log(`500 arr QuickSort ${ Date.now() - t}`)
}()

Answer 1

你自己写个插排、快排，然后自己测量下时间不就知道了。
要么你自己写个标准的插排，再把v8里面用的那个插排弄出来，比较下代码，再测量下时间呗。

Answer 2

快排的时间平均时间复杂度是cNlog(N)，最坏情况下N^2/2,空间复杂度O(log(N))。c是一个常数,经验得出来的一个值。
插入排序平均时间复杂度N^2/4，最坏N^2/2,空间复杂度O(1)。
(上述公式也忽略了一下常数项和N的一次项，因为不是固定的)

所以 N 比较小(v8里给的是10)的时候 N^2/4不见得比 cNlog(N)大，比如设 N<=10,对数的底数取10，c=2.5的时候。
另外同样是一步运算，插入排序只需要比较，交换;而快排需要比较，交换，平均下来的一点儿空间分配。 所以 N 比较小的时候不见得插入排序是慢的。

当 N 比较大的时候上面那些常数的影响可以忽略不计，那么N^2显然是比Nlog(N)大。