It does not change. Stable is a subset of unstable. And vice versa, every unstable algorithm returns a stable result for some inputs. Mark's point is that requiring “always unstable” has no meaning, no matter what language you chose.
/Andreas
正如本文前段所引用的已定稿 ECMAScript 2015 规范中的描述。
时代特点
IMHO，Chrome发布之初即被报告出这个问题可能是有其特殊的时代特点。
上文已经说到，Chrome第一版 是 2008年9月 发布的。根据statcounter的统计数据，那个时期市场占有率最高的两款浏览器分别是 IE(那时候只有IE6和IE7) 和 Firefox，市场占有率分别达到了67.16%和25.77%。也就是说，两个浏览器加起来的市场占有率超过了90%。
而根据另一份浏览器排序算法稳定性的统计数据显示，这两款超过了90%市场占有率的浏览器都采用了稳定的数组排序。所以Chrome发布之初被开发者质疑也是合情合理的。
符合规范
从Bug ISSUE讨论的过程中，可以大概理解开发组成员对于引擎实现采用快速排序的一些考量。
其中一点，他们认为引擎必须遵守ECMAScript规范。由于规范不要求稳定排序的描述，故他们认为 v8 的实现是完全符合规范的。
性能考虑
另外，他们认为 v8 设计的一个重要考量在于引擎的性能。
快速排序 相比较于 归并排序，在整体性能上表现更好：
更高的计算效率。快速排序 在实际计算机执行环境中比同等时间复杂度的其他排序算法更快（不命中最差组合的情况下）
更低的空间成本。前者仅有O(㏒n)的空间复杂度，相比较后者O(n)的空间复杂度在运行时的内存消耗更少
v8在数组排序算法中的性能优化
既然说 v8 非常看中引擎的性能，那么在数组排序中它做了哪些事呢？
通过阅读源代码，还是粗浅地学习了一些皮毛。
混合插入排序
快速排序 是分治的思想，将大数组分解，逐层往下递归。但是若递归深度太大，为了维持递归调用栈的内存资源消耗也会很大。优化不好甚至可能造成栈溢出。
目前v8的实现是设定一个阈值，对最下层的10个及以下长度的小数组使用 插入排序。
根据代码注释以及 Wikipedia 中的描述，虽然插入排序的平均时间复杂度为 O(n²) 差于快速排序的 O(n㏒n)。但是在运行环境，小数组使用插入排序的效率反而比快速排序会更高，这里不再展开。
v8代码示例
var QuickSort = function QuickSort(a, from, to) { ...... while (true) { // Insertion sort is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } ...... } ...... };
三数取中
正如已知的，快速排序的阿克琉斯之踵在于，最差数组组合情况下会算法退化。
快速排序的算法核心在于选择一个基准 (pivot)，将经过比较交换的数组按基准分解为两个数区进行后续递归。试想如果对一个已经有序的数组，每次选择基准元素时总是选择第一个或者最后一个元素，那么每次都会有一个数区是空的，递归的层数将达到 n，最后导致算法的时间复杂度退化为 O(n²)。因此 pivot 的选择非常重要。
v8采用的是 三数取中(median-of-three) 的优化：除了头尾两个元素再额外选择一个元素参与基准元素的竞争。
第三个元素的选取策略大致为：
当数组长度小于等于1000时，选择折半位置的元素作为目标元素。
当数组长度超过1000时，每隔200-215个(非固定，跟着数组长度而变化)左右选择一个元素来先确定一批候选元素。接着在这批候选元素中进行一次排序，将所得的中位值作为目标元素
最后取三个元素的中位值作为 pivot。
v8代码示例
var GetThirdIndex = function(a, from, to) { var t_array = new InternalArray(); // Use both 'from' and 'to' to determine the pivot candidates. var increment = 200 + ((to - from) & 15); var j = 0; from += 1; to -= 1; for (var i = from; i < to; i += increment) { t_array[j] = [i, a[i]]; j++; } t_array.sort(function(a, b) { return comparefn(a[1], b[1]); }); var third_index = t_array[t_array.length >> 1][0]; return third_index; }; var QuickSort = function QuickSort(a, from, to) { ...... while (true) { ...... if (to - from > 1000) { third_index = GetThirdIndex(a, from, to); } else { third_index = from + ((to - from) >> 1); } } ...... };
原地排序
在温习快速排序算法时，我在网上看到了很多用JavaScript实现的例子。
但是发现一大部分的代码实现如下所示