JS数组的排序方法大家肯定用的太多了，那sort用的是什么排序算法呢？这个问题的答案我寻找了很久，最终在Chrome V8引擎的源码中找到了。

说明一下，ECMAScript没有定义使用哪种排序算法，各个浏览器的实现方式会有不同。==火狐中使用的是归并排序，==下面是Chrome的sort排序算法的实现。

sort方法源码

复制 1DEFINE_METHOD(
 2  GlobalArray.prototype,
 3  sort(comparefn) {
 4    CHECK_OBJECT_COERCIBLE(this, "Array.prototype.sort");
 5
 6    if (!IS_UNDEFINED(comparefn) && !IS_CALLABLE(comparefn)) {
 7      throw %make_type_error(kBadSortComparisonFunction, comparefn);
 8    }
 9
10    var array = TO_OBJECT(this);
11    var length = TO_LENGTH(array.length);
12    return InnerArraySort(array, length, comparefn);
13  }
14); 

这一步看出sort方法调用了InnerArraySort方法，参数是数组，数组长度，比较函数。再看看InnerArraySort方法是如何处理的。

InnerArraySort方法源码

复制 1function InnerArraySort(array, length, comparefn) {
 2  // In-place QuickSort algorithm.
 3  // For short (length <= 10) arrays, insertion sort is used for efficiency.
 4
 5  if (!IS_CALLABLE(comparefn)) {
 6    comparefn = function (x, y) {
 7      if (x === y) return 0;
 8      if (%_IsSmi(x) && %_IsSmi(y)) {
 9        return %SmiLexicographicCompare(x, y);
10      }
11      x = TO_STRING(x);
12      y = TO_STRING(y);
13      if (x == y) return 0;
14      else return x < y ? -1 : 1;
15    };
16  }
17  function InsertionSort(a, from, to) {
18    ...
19  };
20 ...
21  function QuickSort(a, from, to) {
22    var third_index = 0;
23    while (true) {
24      // Insertion sort is faster for short arrays.
25      if (to - from <= 10) {
26        InsertionSort(a, from, to);
27        return;
28      }
29      if (to - from > 1000) {
30        third_index = GetThirdIndex(a, from, to);
31      } else {
32        third_index = from + ((to - from) >> 1);
33      }
34      // Find a pivot as the median of first, last and middle element.
35      var v0 = a[from];
36      var v1 = a[to - 1];
37      var v2 = a[third_index];
38      var c01 = comparefn(v0, v1);
39      if (c01 > 0) {
40        // v1 < v0, so swap them.
41        var tmp = v0;
42        v0 = v1;
43        v1 = tmp;
44      } // v0 <= v1.
45      var c02 = comparefn(v0, v2);
46      if (c02 >= 0) {
47        // v2 <= v0 <= v1.
48        var tmp = v0;
49        v0 = v2;
50        v2 = v1;
51        v1 = tmp;
52      } else {
53        // v0 <= v1 && v0 < v2
54        var c12 = comparefn(v1, v2);
55        if (c12 > 0) {
56          // v0 <= v2 < v1
57          var tmp = v1;
58          v1 = v2;
59          v2 = tmp;
60        }
61      }
62      // v0 <= v1 <= v2
63      a[from] = v0;
64      a[to - 1] = v2;
65      var pivot = v1;
66      var low_end = from + 1;   // Upper bound of elements lower than pivot.
67      var high_start = to - 1;  // Lower bound of elements greater than pivot.
68      a[third_index] = a[low_end];
69      a[low_end] = pivot;
70
71      // From low_end to i are elements equal to pivot.
72      // From i to high_start are elements that haven't been compared yet.
73      partition: for (var i = low_end + 1; i < high_start; i++) {
74        var element = a[i];
75        var order = comparefn(element, pivot);
76        if (order < 0) {
77          a[i] = a[low_end];
78          a[low_end] = element;
79          low_end++;
80        } else if (order > 0) {
81          do {
82            high_start--;
83            if (high_start == i) break partition;
84            var top_elem = a[high_start];
85            order = comparefn(top_elem, pivot);
86          } while (order > 0);
87          a[i] = a[high_start];
88          a[high_start] = element;
89          if (order < 0) {
90            element = a[i];
91            a[i] = a[low_end];
92            a[low_end] = element;
93            low_end++;
94          }
95        }
96      }
97      if (to - high_start < low_end - from) {
98        QuickSort(a, high_start, to);
99        to = low_end;
100      } else {
101        QuickSort(a, from, low_end);
102        from = high_start;
103      }
104    }
105  };
106
107  ...
108
109  QuickSort(array, 0, num_non_undefined);
110 ...
111  return array;
112} 

这一步最重要的是QuickSort，从代码和注释中可以看出**==sort使用的是插入排序和快速排序结合的排序算法。**数组长度不超过10时，使用插入排序。长度超过10使用快速排序==。在数组较短时插入排序更有效率。