那么，为什么本机排序较慢？在看代码

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

使用这些方法来防止最坏情况的合并排序比快速排序更快，但是合并排序需要的辅助数组的大小与原始数组的大小相同或一半。

Introsort是quicksort和heapsort的混合体，如果递归级别太深，则切换到heapsort是一种替代方法：

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

下面的第二个合并排序示例使用一个compare函数进行公平的比较。它比本机版本快得多。对于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, aux, lo, mid, 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, aux, lo, hi) {

    if (hi < lo) return;

    if (hi == lo){

        aux[lo] = arr[lo];

        return;

    }

    var mid = Math.floor(lo + (hi - lo) / 2);

    sortarrtoarr(arr, aux, lo, mid);

    sortarrtoarr(arr, aux, mid + 1, hi);

    merge(arr, aux, lo, mid, hi);

  }



  function sortarrtoarr(arr, aux, lo, hi) {

    if (hi <= lo) return;

    var mid = Math.floor(lo + (hi - lo) / 2);

    sortarrtoaux(arr, aux, lo, mid);

    sortarrtoaux(arr, aux, mid + 1, hi);

    merge(aux, arr, lo, mid, hi);

  }



  function merge_sort(arr) {

    var aux = arr.slice(0);

    sortarrtoarr(arr, aux, 0, 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, aux, lo, mid, 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, aux, lo, hi, comparefn) {

    if (hi < lo) return;

    if (hi == lo){

        aux[lo] = arr[lo];

        return;

    }

    var mid = Math.floor(lo + (hi - lo) / 2);

    sortarrtoarr(arr, aux, lo, mid, comparefn);

    sortarrtoarr(arr, aux, mid + 1, hi, comparefn);

    merge(arr, aux, lo, mid, hi, comparefn);

  }



  function sortarrtoarr(arr, aux, lo, hi, comparefn) {

    if (hi <= lo) return;

    var mid = Math.floor(lo + (hi - lo) / 2);

    sortarrtoaux(arr, aux, lo, mid, comparefn);

    sortarrtoaux(arr, aux, mid + 1, hi, comparefn);

    merge(aux, arr, lo, mid, hi, comparefn);

  }



  function merge_sort(arr, comparefn) {

    var aux = arr.slice(0);

    sortarrtoarr(arr, aux, 0, 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, i];

}



console.time('measure');

arr.sort(function compareNumbers(a, 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][1]);

        console.log(arr[i  ][0], arr[i  ][1]);

        break;

    }

}