v8--sort 方法 源码 的 插入排序法

function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      // Pre-convert the element to a string for comparison if we know
      // it will happen on each compare anyway.
      var key =
          (custom_compare || %_IsSmi(element)) ? element : ToString(element);
      // place element in a[from..i[
      // binary search
      var min = from;
      var max = i;
      // The search interval is a[min..max[
      while (min < max) {
        var mid = min + ((max - min) >> 1);
        var order = Compare(a[mid], key);
        if (order == 0) {
          min = max = mid;
          break;
        }
        if (order < 0) {
          min = mid + 1;
        } else {
          max = mid;
        }
      }
      // place element at position min==max.
      for (var j = i; j > min; j--) {
        a[j] = a[j - 1];
      }
      a[min] = element;
    }
  }

function insertSort(arr) {

  for(let i= 1; i < arr.length; i++) {
    let key = arr[i] // 哨兵，保存当前循环索引对应的值

    let min = 0 // 插值位置
    let max = i // 已循环次数

    // 遍历已循环的数组，找寻插值位置
    while(min < max) {
      // 中值 >>有符号右移 类似于 Math.floor(int/2) int是正整数
      let mid = min + ((max - min) >>1)         
      // 比较函数，传入索引中值对应的值和哨兵
      const order = compare(a[mid], key)

      // 如果等于0 
      if (order === 0) {
        // 把mid赋值给min。作为插值位置，退出循环
        min = max = mid
        break;
      }
      /**
       * 已循环的数组是有序的数组，索引中值对应的值与哨兵比较
       * 小于则将mid赋值给min，继续取min与max值的中值。然后比较该中值对应的值与哨兵的大小
       * 大于则将中值赋值给max值，在取min与新max的中值，然后比较该中值对应的值与哨兵的大小
       * 循环往复，直到min = max，退出该循环，找到插入点
      */
      if (order < 0) {
        min = mid + 1
      } else {
        max = mid
      }
    }

    /**
     * 插入操作循环，从已循环数组的末尾开始，依次把上一个索引值赋给当前索引值
     * 如： a[3] = a[2] a[2] = a[1]，一直到插值位置min。
     * 循环结束后，把哨兵赋值给arr[min]
     * 
    */
    for (let j = i; j > min; j--) {
      arr[j] = arr[j - 1]
    }
    arr[min] = key
  }
}