Google V8 JavaScript Engine のソートメソッド

って，こうらしい

// google-v8 javascript engine (on macosx)
var array = [];
print (array.sort)
// 以下結果
function sort(comparefn) {
  var custom_compare = (typeof(comparefn) === 'function');
  function Compare(x,y) {
    if (custom_compare) {
      return comparefn.call(null, x, y);
    }
    if (_IsSmi(x) && _IsSmi(y)) {
      return SmiLexicographicCompare(x, y);
    }
    x = ToString(x);
    y = ToString(y);
    if (x == y) return 0;
    else return x < y ? -1 : 1;
  };
  function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      var min = from;
      var max = i;
      while (min < max) {
        var mid = min + ((max - min) >> 1);
        var order = Compare(a[mid], element);
        if (order == 0) {
          min = max = mid;
          break;
        }
        if (order < 0) {
          min = mid + 1;
        } else {
          max = mid;
        }
      }
      for (var j = i; j > min; j--) {
        a[j] = a[j - 1];
      }
      a[min] = element;
    }
  }
  function QuickSort(a, from, to) {
    if (to - from <= 22) {
      InsertionSort(a, from, to);
      return;
    }
    var pivot_index = $floor($random() * (to - from)) + from;
    var pivot = a[pivot_index];
    a[pivot_index] = a[to - 1];
    a[to - 1] = pivot;
    var low_end = from;
    var high_start = to - 1;
    for (var i = from; i < high_start; ) {
      var element = a[i];
      var order = Compare(element, pivot);
      if (order < 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
        i++;
      } else if (order > 0) {
        high_start--;
        a[i] = a[high_start];
        a[high_start] = element;
      } else {
        i++;
      }
    }
    a[to - 1] = a[high_start];
    a[high_start] = pivot;
    high_start++;
    QuickSort(a, from, low_end);
    QuickSort(a, high_start, to);
  }
  var old_length = ToUint32(this.length);
  RemoveArrayHoles(this);
  var length = ToUint32(this.length);
  for (var i = 0; i < length; ) {
    if ((typeof(this[i]) === 'undefined')) {
      length--;
      this[i] = this[length];
      this[length] = void 0;
    } else {
      i++;
    }
  }
  QuickSort(this, 0, length);
  if (HasArrayClass(this)) {
    this.length = old_length;
  }
  return this;
} 

内部的にはQuickSortとInsertionSortの併用になってるんですね．

個数が減ってきたらInsertionSortの方が有効という理由からですかね．*1

*1:クイックソート-Wikipedia