V8数组排序方法sort浅析

摘要：出于性能优化的目的，当数组排序区间长度在之内时，实际的排序方法是插入排序，其余时候使用快速排序。大体上，这个排序方法的思想是对数组进行区间划分，当排序区间大于时，使用快排，使局部有序，当区间小于等于时使用插入排序，使数组整体有序。

数组提供了排序方法，使用时传入一个比较函数，根据比较函数的返回来确定元素最终在数组中的位置。默认排序顺序是根据字符串Unicode码点。

var a = [12,4,6,8,9,54,11,13];
a.sort(); // [11, 12, 13, 4, 54, 6, 8, 9]

如果指明了比较函数，那么数组会按照调用该函数的返回值排序。比较函数接受两个参数(x,y)，表示数组中待排序的元素，根据返回结果来决定如何排序：

返回结果小于0，表示x在前y在后。

返回结果等于0，则x和y位置不改变。（备注： ECMAScript 标准并不要求这一行为，说明sort排序不一定是稳定的）

返回结果大于0，表示x应该在y之后。

在MDN中还特别指出，无法保证排序的时间和空间复杂性。这是因为不同引擎实现排序方法的方式不一定相同。

函数的整体结构如下，当参数不是可执行的比较函数时，内部定义默认的比较函数。

出于性能优化的目的，当数组排序区间长度在10之内时，实际的排序方法是插入排序，其余时候使用快速排序。所以定义了内部函数InsertionSort和QuickSort，同时还有函数GetThirdIndex，用于辅助快排中支点的选择。

// TODO(pwong): Remove once TypedArray.prototype.join() is ported to Torque.
function InnerArraySort(array, length, comparefn) {
  // In-place QuickSort algorithm.
  // For short (length <= 10) arrays, insertion sort is used for efficiency.

  if (!IS_CALLABLE(comparefn)) {
    comparefn = function (x, y) {
        // ...
    };
  }
  function InsertionSort(a, from, to) {
    // ...
  };

  function GetThirdIndex(a, from, to) {
    // ...
  }

  function QuickSort(a, from, to) {
    // ...
  };

  if (length < 2) return array;

  var num_non_undefined = %PrepareElementsForSort(array, length);

  QuickSort(array, 0, num_non_undefined);

  return array;
}

下面来逐段分析代码。

第一个if处理默认排序，内部会将x、y转化成字符串再进行比较。字符串比较是使用基于标准字典的 Unicode 值来进行比较的，这也是第一个例子中13在4之前的原因。

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

接着实现了插入排序。模拟将新元素插入到数组中间的过程，从第二个元素from + 1开始，根据大小关系确定插入的位置。当确定插入位置在j的时候，原在j上以及后面的元素都要向右移一，索引加一。这就是插入排序。

插入排序每次排序过程会将当前元素与前面的元素进行比较。以升序排序为例，循环将当前元素与前一元素比较，当前元素较小时交换两个元素的位置，直至当前元素大于前一元素或到达排序区间的第一位时结束循环，完成当前元素的排序。更新新元素位置时的遍历区间是[from, i]，i的取值是[from + 1, to]。

使用element缓存插入排序中要插入的值，每次迭代中，使用tmp缓存a[j]的值，执行comparefn(tmp, element)。

返回结果order大于0的时候，说明element仍需向前，所以要将a[j]向后移动。a[j + 1] = tmp便完成了这样的工作；直至order大于等于0，说明则找到element应插入的位置，执行a[j + 1] = element插入a[i]。

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

如图示，使用插入排序使数组升序，上箭头表示当前循环中的i，当前缓存值element是19，下箭头是j，从i - 1开始想前遍历，如果element应在a[j]之前，则a[j + 1] = tmp，确定插入位置时，a[j + 1] = element。这样就完成了一个元素的插入过程。

当数组长度较长时，内部使用快速排序。快排的思想是选取某一个值作为支点值，先从头遍历，找出第一个应该在支点值右边的元素，再从尾向头遍历，找出第一个应该在支点值左边的元素，交换两个元素，直至左边与右边重叠。重叠的位置即是支点应在的位置。以升序排序为例，支点左边的值均小于等于支点值，右边的值均大于支点值。

在V8引擎的实现中，支点值的选取是确定第三个值，再取其与a[from]、a[to]的中值作为支点值。当排序区间的长度在1000以内时，第三个值的位置是from + ((to - from) >> 1)，接近区间的中值点。当排序区间较大时(大于1000)，第三个值的索引是通过GetThirdIndex来获取。GetThirdIndex的选取思想是将区间分成多段，每段用一个值代表，然后从这些值去选取一个接近中值的值作为支点。

increment是区间分段后每段的长度，取值区间是[200, 215]。分段的范围是[from + 1, to - 1]，每一段用起点值代表。将代表值及其在原数组a中的索引保存在数组中作为内部数组t_array的元素，并根据代表值进行排序。

最后的返回结果是t_array[t_array.length >> 1][0]。t_array.length >> 1是将t_array.length的二进制形式左移一位，取值接近t_array的中值，t_array[t_array.length >> 1][0]则是这个中值在数组a中的索引。

  function GetThirdIndex(a, from, to) {
    var t_array = new InternalArray();
    // Use both "from" and "to" to determine the pivot candidates.
    var increment = 200 + ((to - from) & 15);
    var j = 0;
    from += 1;
    to -= 1;
    for (var i = from; i < to; i += increment) {
      t_array[j] = [i, a[i]];
      j++;
    }
    t_array.sort(function(a, b) {
      return comparefn(a[1], b[1]);
    });
    var third_index = t_array[t_array.length >> 1][0];
    return third_index;
  }

快排的实现如下。

内部使用一个while(true)循环，只有当to - from <= 10才会结束无限循环。在函数内末尾有修改from/to的代码，避免无限循环，同时递归调用自身。大体上，这个排序方法的思想是对数组进行区间划分，当排序区间大于10时，使用快排，使局部有序，当区间小于等于10时使用插入排序，使数组整体有序。

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 - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }
    }
    
  }

第三个点的位置会根据排序区间的长度来选取。

      if (to - from > 1000) {
        third_index = GetThirdIndex(a, from, to);
      } else {
        third_index = from + ((to - from) >> 1);
      }

将a[from]/a[to-1]和上面选取的第三个点的值记为v0、v1、v2。交换这些值，使其按v0 <= v1 <= v2的顺序排列。

      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;

如果忽略from之前与to之后的元素，当前的排序区间可以表示成

随后，交换low_end与third_index的值。

      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;

现在排序区间的结构如下:

接着从low_end + 1开始向右遍历，令element = a[i]，比较当前元素element与pivot。若comparefn(element, pivot) < 0，说明element应该在pivot前，将element与a[low_end](即pivot)交换，low_end++表示pivot位置向右移一位，因为原来的位置已变成element。

如果comparefn(element, pivot) > 0说明element应该在pivot后，从high_start开始向左查找第一个应该在pivot前或与pivot相等的元素top_elem，交换top_elem与element。如果top_elem应该在pivot之前，二者互换。如果comparefn(element, pivot) == 0，则element/pivot取值相同，无需交换，同时也无需移动low_end。

直至i == high_start时退出循环。下面是上述流程完整的代码。

      // 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++;
          }
        }
      }

完成整个快排的数组区间以a[i]/pivot为分界点，a[i]左边的元素全小于或等于pivot，a[i]右边的元素全大于pivot。然后从[from, low_end]和[high_start, to]中选出区间较小的一组递归调用QuickSort；同时将更新一个端点，缩小区间。

      if (to - high_start < low_end - from) {
        QuickSort(a, high_start, to);
        to = low_end;
      } else {
        QuickSort(a, from, low_end);
        from = high_start;
      }

这是完整的快排算法。

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

Array.prototype.sort() - MDN

V8的排序方法实现