var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); };
以上代码的主要问题在于：利用 left 和 right 两个数区存储递归的子数组，因此它需要 O(n) 的额外存储空间。这与理论上的平均空间复杂度 O(㏒n) 相比差距较大。
额外的空间开销，同样会影响实际运行时的整体速度。这也是快速排序在实际运行时的表现可以超过同等时间复杂度级别的其他排序算法的其中一个原因。所以一般来说，性能较好的快速排序会采用原地 (in-place) 排序的方式。
v8 源代码中的实现是对原数组进行元素交换。
Firefox为什么采用归并排序
它的背后也是有故事的。
Firefox其实在一开始发布的时候对于数组排序的实现并不是采用稳定的排序算法，这块有据可考。
Firefox(Firebird)最初版本 实现的数组排序算法是 堆排序，这也是一种不稳定的排序算法。因此，后来有人对此提交了一个Bug。
Mozilla开发组内部针对这个问题进行了一系列讨论。
从讨论的过程我们能够得出几点
1.同时期 Mozilla 的竞争对手是 IE6，从上文的统计数据可知IE6是稳定排序的
2.JavaScript之父 Brendan Eich 觉得 Stability is good
3.Firefox在采用 堆排序 之前采用的是 快速排序
基于开发组成员倾向于实现稳定的排序算法为主要前提，Firefox3 将 归并排序 作为了数组排序的新实现。
解决排序稳定性的差异
以上说了这么多，主要是为了讲述各个浏览器对于排序实现的差异，以及解释为什么存在这些差异的一些比较表层的原因。
但是读到这里，读者可能还是会有疑问：如果我的项目就是需要依赖稳定排序，那该怎么办呢？
解决方案
其实解决这个问题的思路比较简单。
浏览器出于不同考虑选择不同排序算法。可能某些偏向于追求极致的性能，某些偏向于提供良好的开发体验，但是有规律可循。
从目前已知的情况来看，所有主流浏览器（包括IE6，7，8）对于数组排序算法的实现基本可以枚举：
1.归并排序 / Timsort
2.快速排序
所以，我们将快速排序经过定制改造，变成稳定排序的是不是就可以了？
一般来说，针对对象数组使用不稳定排序会影响结果。而其他类型数组本身使用稳定排序或不稳定排序的结果是相等的。因此方案大致如下：
将待排序数组进行预处理，为每个待排序的对象增加自然序属性，不与对象的其他属性冲突即可。
自定义排序比较方法compareFn，总是将自然序作为前置判断相等时的第二判断维度。
面对归并排序这类实现时由于算法本身就是稳定的，额外增加的自然序比较并不会改变排序结果，所以方案兼容性比较好。
但是涉及修改待排序数组，而且需要开辟额外空间用于存储自然序属性，可想而知 v8 这类引擎应该不会采用类似手段。不过作为开发者自行定制的排序方案是可行的。
方案代码示例
'use strict'; const INDEX = Symbol('index'); function getComparer(compare) { return function (left, right) { let result = compare(left, right); return result === 0 ? left[INDEX] - right[INDEX] : result; }; } function sort(array, compare) { array = array.map( (item, index) => { if (typeof item === 'object') { item[INDEX] = index; } return item; } ); return array.sort(getComparer(compare)); }
以上只是一个简单的满足稳定排序的算法改造示例。
之所以说简单，是因为实际生产环境中作为数组输入的数据结构冗杂，需要根据实际情况判断是否需要进行更多样的排序前类型检测。
标注
1.前端现在已经是一个比较宽泛的概念。本文中的前端主要指的是以浏览器作为载体，以 JavaScript 作为编程语言的环境
2.本文无意于涉及算法整体，谨以常见的排序算法作为切入点
3.在确认 Firefox 数组排序实现的算法时，搜到了 SpiderMoney 的一篇排序相关的Bug。大致意思是讨论过程中有人建议用极端情况下性能更好的 Timsort 算法替换 归并排序，但是 Mozilla 的工程师表示由于 Timsort 算法存在License授权问题，没办法在 Mozilla 的软件中直接使用算法，等待对方的后续回复
总结