unction ArraySort(comparefn) {

// In-place QuickSort algorithm.

// For short (length <= 22) arrays, insertion sort is used for efficiency.

var custom_compare = IS_FUNCTION(comparefn)

function Compare(x,y) {

// Assume the comparefn, if any, is a consistent comparison function.

// If it isn't, we are allowed arbitrary behavior by ECMA 15.4.4.11.

if (x === y) return 0

if (custom_compare) {

// Don't call directly to avoid exposing the builtin's global object.

return comparefn.call(null, x, y)

}

if (%_IsSmi(x) &&%_IsSmi(y)) {

return %SmiLexicographicCompare(x, y)

}

x = ToString(x)

y = ToString(y)

if (x == y) return 0

else return x <y ? -1 : 1

}

function InsertionSort(a, from, to) {

for (var i = from + 1i <toi++) {

var element = a[i]

// Pre-convert the element to a string for comparison if we know

// it will happen on each compare anyway.

var key =

(custom_compare || %_IsSmi(element)) ? element : ToString(element)

// place element in a[from..i[

// binary search

var min = from

var max = i

// The search interval is a[min..max[

while (min <max) {

var mid = min + ((max - min) >>1)

var order = Compare(a[mid], key)

if (order == 0) {

min = max = mid

break

}

if (order <0) {

min = mid + 1

} else {

max = mid

}

}

// place element at position min==max.

for (var j = ij >minj--) {

a[j] = a[j - 1]

}

a[min] = element

}

}

function QuickSort(a, from, to) {

// Insertion sort is faster for short arrays.

if (to - from <= 22) {

InsertionSort(a, from, to)

return

}

var pivot_index = $floor($random() * (to - from)) + from

var pivot = a[pivot_index]

// Pre-convert the element to a string for comparison if we know

// it will happen on each compare anyway.

var pivot_key =

(custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot)

// Issue 95: Keep the pivot element out of the comparisons to avoid

// infinite recursion if comparefn(pivot, pivot) != 0.

a[pivot_index] = a[from]

a[from] = pivot

var low_end = from // Upper bound of the elements lower than pivot.

var high_start = to // Lower bound of the elements greater than pivot.

// From low_end to i are elements equal to pivot.

// From i to high_start are elements that haven't been compared yet.

for (var i = from + 1i <high_start) {

var element = a[i]

var order = Compare(element, pivot_key)

if (order <0) {

a[i] = a[low_end]

a[low_end] = element

i++

low_end++

} else if (order >0) {

high_start--

a[i] = a[high_start]

a[high_start] = element

} else { // order == 0

i++

}

}

QuickSort(a, from, low_end)

QuickSort(a, high_start, to)

}

var old_length = ToUint32(this.length)

if (old_length <2) return this

%RemoveArrayHoles(this)

var length = ToUint32(this.length)

// Move undefined elements to the end of the array.

for (var i = 0i <length) {

if (IS_UNDEFINED(this[i])) {

length--

this[i] = this[length]

this[length] = void 0

} else {

i++

}

}

QuickSort(this, 0, length)

// We only changed the length of the this object (in

// RemoveArrayHoles) if it was an array. We are not allowed to set

// the length of the this object if it is not an array because this

// might introduce a new length property.

if (IS_ARRAY(this)) {

this.length = old_length

}

return this

}

js提供了sort方法，方便对数组进行排序，然而不同引擎对js的sort方法解析可能存在差异。本文基于v8引擎进行分析。

在v8引擎中，对sort方法提供了2种排序算法：插入排序及快排序。

sort使用方法：

当没有参数传入的时候，其排序顺序默认为，将待排序数据转换为字符串，并按照 Unicode 序列排序；当然，比较函数可以自定义，自定义排序函数需要返回值，其返回值为 -1，0，1 ，分别表示 a<b, a=b, a>b.

当数组长度小于等于10的时候，采用插入排序，大于10的时候，采用快排。

对于长度大于1000的数组，采用的是快排与插入排序混合的方式进行排序的，因为，当数据量很小的时候，插入排序效率优于快排。

快排的平均时间复杂度是nlogn，在排序算法中属于效率最高的。快排是一种不稳定的排序算法，但是一般情况下稳定或者不稳定对我们没有特别大的影响，但是对稳定性要求高的排序，就不能使用快排了。

原文： https://zhuanlan.zhihu.com/p/33626637

sort函数执行时，会依次循环把数组里的两个数传递给函数f，这时候f的参数a和b就分别是传入的两个数，然后分别求出a和b除以2的余数（实际上就是判断a和b是奇数还是偶数，0是偶数，1是奇数）。如果a是偶数，函数f就返回1（或其他任何大于0的数），如果a是奇数且b是偶数就返回-1（或其他任何小于0的数）。sort函数根据f的返回值来对两个数进行排序，如果是大于0的数，就把两个数的值对调，如果是0或小于0的数则不做任何处理。

这样的话，当数组中的所有元素都两两处理完毕后，最终就会形成奇数在前偶数在后的情况了。

---