那么，为什么本机排序较慢？在看代码
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 secondsRelu's quick sort - 1.3 secondsoptimized merge sort - 1.4 secondsoptimized merge sort with compare - 1.8 seconds
使用Chrome的结果（时间略有不同）
native sort - 5.3 secondsRelu's merge sort - 2.1 secondsRelu's quick sort - 1.8 secondsoptimized merge sort - 1.6 secondsoptimized 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 resultfor (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; }}
