https://github.com/v8/v8/blob/0c76b0ae850027006d5ec0d92449e449d996d3bb/src/js/array.js#L744

这个问题似乎是GetThirdIndex().当分区大小为>时调用1000,我假定它用于防止快速排除最坏情况的性能,但是开销是重要的,因为它创建了内部的对数组并对其进行排序,并且这些对的排序可能导致对GetThirdIndex()的进一步的递归调用.这与与分割原始阵列相关的递归调用和对内部数组对进行分区相结合.

由于这些示例的测试数据是随机数据,所以Relu的quicksort不需要像GetThirdIndex()这样的东西.还有对阵列中的“孔”的检查,但是我认为这并不重要.

GetThirdIndex()的替代方案将是中位数的中位数：

http://en.wikipedia.org/wiki/Median_of_medians

合并排序比quicksort快,这些方法用于防止最坏的情况,但它需要与原始数组相同大小或一半大小的辅助数组.

Introsort是快速排序和堆叠的混合,如果递归级别太深,可以转换为堆积,这将是另一种选择：

http://en.wikipedia.org/wiki/Introsort

下面的第二个合并排序示例使用比较函数进行比较.它比本机版本快得多.在Chrome的情况下,比较功能并没有影响整体的时间.在Firefox的情况下,比较功能更有效果.在Firefox的情况下,本机版本的内存不足,所以我无法比较.

这些是自上而下合并排序的一些更快的版本,原始海报“好奇”,使用相互递归函数来避免复制和稍微优化的merge()(每个比较两个条件).

Firefox的结果(时间有所不同)

native sort - Failed for out of memory.
Relu's merge sort - 1.8 seconds
Relu's quick sort - 1.3 seconds
optimized merge sort - 1.4 seconds
optimized merge sort with compare - 1.8 seconds

Chrome结果(时间有所不同)

native sort - 5.3 seconds
Relu's merge sort - 2.1 seconds
Relu's quick sort - 1.8 seconds
optimized merge sort - 1.6 seconds
optimized merge sort with compare - 1.7 seconds

合并排序

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
  function merge(arr,hi) {
    var i = lo;
    var j = mid + 1;
    var k = lo;
    while(true){
      if(arr[i] <= arr[j]){
        aux[k++] = arr[i++];
        if(i > mid){
          do
            aux[k++] = arr[j++];
          while(j <= hi);
          break;
        }
      } else {
        aux[k++] = arr[j++];
        if(j > hi){
          do
            aux[k++] = arr[i++];
          while(i <= mid);
          break;
        }
      }
    }
  }

  function sortarrtoaux(arr,hi) {
    if (hi < lo) return;
    if (hi == lo){
        aux[lo] = arr[lo];
        return;
    }
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoarr(arr,mid);
    sortarrtoarr(arr,hi);
    merge(arr,hi);
  }

  function sortarrtoarr(arr,hi) {
    if (hi <= lo) return;
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoaux(arr,mid);
    sortarrtoaux(arr,hi);
    merge(aux,arr,hi);
  }

  function merge_sort(arr) {
    var aux = arr.slice(0);
    sortarrtoarr(arr,arr.length - 1);
    return arr;
  }

  return merge_sort(array);
}

console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0],arr[1]);

合并排序与比较功能

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array,comparefn) {
  function merge(arr,hi,comparefn) {
    var i = lo;
    var j = mid + 1;
    var k = lo;
    while(true){
      var cmp = comparefn(arr[i],arr[j]);
      if(cmp <= 0){
        aux[k++] = arr[i++];
        if(i > mid){
          do
            aux[k++] = arr[j++];
          while(j <= hi);
          break;
        }
      } else {
        aux[k++] = arr[j++];
        if(j > hi){
          do
            aux[k++] = arr[i++];
          while(i <= mid);
          break;
        }
      }
    }
  }

  function sortarrtoaux(arr,comparefn) {
    if (hi < lo) return;
    if (hi == lo){
        aux[lo] = arr[lo];
        return;
    }
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoarr(arr,comparefn);
    sortarrtoarr(arr,comparefn);
    merge(arr,comparefn);
  }

  function sortarrtoarr(arr,comparefn) {
    if (hi <= lo) return;
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoaux(arr,comparefn);
    sortarrtoaux(arr,comparefn);
    merge(aux,comparefn);
  }

  function merge_sort(arr,comparefn) {
    var aux = arr.slice(0);
    sortarrtoarr(arr,arr.length - 1,comparefn);
    return arr;
  }

  return merge_sort(array,comparefn);
}

console.time('measure');
mergeSort(arr,function compareNumbers(a,b) {
  return a - b;
});
console.timeEnd('measure');
// check result
for (let i = 1; i < length; i++) {
    if(arr[i] < arr[i-1]){
        console.log('error');
        break;
    }
}
console.log(arr[0],arr[1]);

旁注：本机排序不稳定：

本机JavaScript排序 – 测试稳定性

var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
  j = parseInt(Math.random() * 100);
  arr[i] = [j,i];
}

console.time('measure');
arr.sort(function compareNumbers(a,b) {
  return a[0] - b[0];
});
console.timeEnd('measure');

for (let i = 1; i < length; i++) {
    if( (arr[i][0] == arr[i-1][0]) &&
        (arr[i][1] <  arr[i-1][1]) ){
        console.log('not stable');
        console.log(arr[i-1][0],arr[i-1][1]);
        console.log(arr[i  ][0],arr[i  ][1]);
        break;
    }
}

本机Javascript排序 – 更改比较使其稳定

var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
  j = parseInt(Math.random() * 100);
  arr[i] = [j,b) {
  if(a[0] == b[0])
    return a[1] - b[1];
  return a[0] - b[0];
});
console.timeEnd('measure');

for (let i = 1; i < length; i++) {
    if( (arr[i][0] == arr[i-1][0]) &&
        (arr[i][1] <  arr[i-1][1]) ){
        console.log('not stable');
        console.log(arr[i-1][0],arr[i  ][1]);
        break;
    }
}