# 从V8 sort源码看插入排序

[3, 11, 2].sort() // [11, 2, 3]

[3, 11, 2].sort((a,b) => a < b) // [3, 11, 2]
[3, 11, 2].sort((a,b) => a > b) // [3, 11, 2]

[3, 11, 2].sort((a,b) => a - b) // [2, 3, 11]
[3, 11, 2].sort((a,b) => b - a) // [11, 3, 2]
 
        Copied!
    

function ArraySort(comparefn) {
  CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");

  var array = TO_OBJECT(this);
  var length = TO_LENGTH(array.length);
  return InnerArraySort(array, length, comparefn);
}
 
        Copied!
    

function InnerArraySort(array, length, comparefn) {
    // 未定义comparefn时，会转为string对比
    if (!IS_CALLABLE(comparefn)) {
        comparefn = function (x, y) {
        if (x === y) return 0;
        if (%_IsSmi(x) && %_IsSmi(y)) {
            return %SmiLexicographicCompare(x, y);
        }
        x = TO_STRING(x);
        y = TO_STRING(y);
        if (x == y) return 0;
        else return x < y ? -1 : 1;
        };
    }
    var QuickSort = 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;
        }
        // 数据较多时，递归处理
        if (to - from > 1000) {
            third_index = GetThirdIndex(a, from, to);
        } else {
            third_index = from + ((to - from) >> 1);
        }
        // Find a pivot as the median of first, last and middle element.
        ...
        if (to - high_start < low_end - from) {
            QuickSort(a, high_start, to);
            to = low_end;
        } else {
            QuickSort(a, from, low_end);
            from = high_start;
        }
        }
    };

    QuickSort(array, 0, num_non_undefined);
    return array
}
 
        Copied!
    

// 插入排序
/**
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

1. 从第一个元素开始，该元素可以认为已经被排序
1. 取出下一个元素，在已经排序的元素序列中从后向前扫描
1. 如果该元素（已排序）大于新元素，将该元素移到下一位置
1. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
1. 将新元素插入到该位置后
1. 重复步骤2~5
**/
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;
    }
  };
 
        Copied!