# 从V8 sort源码看插入排序

有个好友问了如下Array.prototype.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]
    

感觉很奇怪吧，看下MDN (opens new window) (opens new window)解释：

• If compareFunction is not supplied
  • all non-undefined array elements are sorted by converting them to strings and comparing strings in UTF-16 code units order.
• If compareFunction is supplied
  • If compareFunction(a, b) is less than 0, sort a to an index lower than b (i.e. a comes first).
  • If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements. Note: the ECMAscript standard does not guarantee this behavior, thus, not all browsers (e.g. Mozilla versions dating back to at least 2003) respect this.
  • If compareFunction(a, b) is greater than 0, sort b to an index lower than a (i.e. b comes first).
  • compareFunction(a, b) must always return the same value when given a specific pair of elements a and b as its two arguments. If inconsistent results are returned, then the sort order is undefined.

compareFunction结果有三种：0（顺序不变），>0（从小到大）,<0（从大到小）。如果是a>b形式返回true/false，自动转为number就变成1/0两种结果了

# V8源码

    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);
    }
    

    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
    }
    

# 插入排序

插入排序 (opens new window) (opens new window)（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

打扑克牌时，从牌桌上逐一拿起扑克牌，在手上排序的过程相同。

举例：

Input: {5 2 4 6 1 3}。

首先拿起第一张牌, 手上有 {5}。

拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。

拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。

以此类推。

    // 插入排序
    /**
    一般来说，插入排序都采用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;
        }
      };