1、找出 Array.prototype.sort 使用的什么排序算法

2、用一种直观的方式展示 Array.prototype.sort 的时间复杂度，看看它有多快？

V8 引擎的一段注释

// In-place QuickSort algorithm.
// For short (length <= 10) arrays, insertion sort is used for efficiency.

Google Chrome 对 sort 做了特殊处理，对于长度 <= 10 的数组使用的是插入排序(稳定排序算法) ，>10 的数组使用的是快速排序。快速排序是不稳定的排序算法。

但是很明显比我们常见的快速排序要复杂得多，不过核心算法还是快速排序。算法复杂的原因在于 v8 出于性能考虑进行了很多优化。

再看 safari Nitro 引擎的一段代码：

if (typeof comparator == "function")
  comparatorSort(array, length, comparator);
else if (comparator === null || comparator === @undefined)
  stringSort(array, length);

  省略....

function stringSort(array, length)
{
  var valueCount = compact(array, length);

  var strings = @newArrayWithSize(valueCount);
  for (var i = 0; i < valueCount; ++i)
      strings[i] = { string: @toString(array[i]), value: array[i] };

  bucketSort(array, 0, strings, 0);
}

  省略....

function comparatorSort(array, length, comparator)
{
  var valueCount = compact(array, length);
  mergeSort(array, valueCount, comparator);
}

默认使用的桶排序，如果 sort 传入的自定义函数作为参数，就是用归并排序（稳定排序算法）

Firefox 源码就不贴了，上面的表格有源码地址，使用的稳定排序算法 — 归并算法。
Microsoft Edge 和 IE(9+) 使用的不稳定排序算法 - 快速排序。
但是 IE（6、7、8）使用的稳定算法。

算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，
进而分析T(n)随着n的变化情况并确定T(n)的数量级。
算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))。
它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，
称作算法的时间复杂度，简称为时间复杂度。
其中f(n)是问题规模n的某个函数。
常用的时间复杂度所耗费的时间从小到大依次是

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)

算法的时间复杂度与运行时间有一些常见的比例关系
维基百科关于算法稳定性的解释
当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。

(4, 1) (3, 1) (3, 7)（5, 6）

在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (维持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6) （次序被改变）

排序算法不稳定有什么影响

举个例子：

某市的机动车牌照拍卖系统，最终中标的规则为：

1、按价格进行倒排序；

2、相同价格则按照竞标顺位（即价格提交时间）进行正排序。

排序若是在前端进行，那么采用快速排序的浏览器中显示的中标者很可能是不符合预期的。