The problems to be solved in this paper

1, find out what sort algorithm array.prototype. sort uses

Show array.prototype. sort’s time complexity in an intuitive way and see how fast it is.

3. Problems to be paid attention to in actual development

Array.prototype.sortEach browser algorithm implementation

ECMAScript 5.1

ECMAScript 6.0

ECMAScript draft

Array.prototype.sort is not specified in the ECMAScript definitions for array.prototype. sort. There is also no requirement to use a stable algorithm (which is explained below).

Therefore, each browser provides its own implementation:

The table is partly from Wikipedia

The browser JavaScript engine used Sorting algorithm The source address
Google Chrome V8 Insert sort and quicksort sortThe source code to achieve
Mozilla Firefox SpiderMonkey Merge sort sortThe source code to achieve
Safari Nitro (JavaScriptCore) Merge sort and bucket sort sortThe source code to achieve
Microsoft Edge and IE (9 +) Chakra Quick sort sortThe source code to achieve

Source code analysis

A note on the V8 engine

// In-place QuickSort algorithm.

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

Google Chrome makes a special case for sort, using insertion sort (stable sort algorithm) for arrays <= 10 and quicksort for arrays >10. Quicksort is an unstable sorting algorithm.

But it’s obviously a lot more complicated than the quicksort that we’re used to, but the core algorithm is still quicksort. The reason for the complexity of the algorithm is that V8 has been optimized for performance.

Take another look at the safari Nitro engine

if (typeof comparator == "function") comparatorSort(array, length, comparator); else if (comparator === null || comparator === @undefined) stringSort(array, length); Omit... 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); } to omit... function comparatorSort(array, length, comparator) { var valueCount = compact(array, length); mergeSort(array, valueCount, comparator); }Copy the code

The default bucket sort, if passed by sort as a custom function, is merge sort (stable sort algorithm)

Firefox source code is not posted, the above table has source address, the use of stable sorting algorithm – merge algorithm. Microsoft Edge and IE(9+) use an unstable sorting algorithm – quicksort. But the stable algorithm used by IE (6, 7, 8).

A comparison of algorithms

Sorting type On average The best situation The worst Auxiliary space The stability of
Quick sort O(nlogn) O(nlogn) O (n squared) O(nlogn) unstable
Merge sort O(nlogn) O(nlogn) O(nlogn) O(n) stable
Insertion sort O (n squared) O(n) O (n squared) O(1) stable
Bucket sort O(n+k) O(n+k) O (n squared) O(n+k) (Unstable)

Note: The stability of bucket sort depends on the stability of bucket sort, so its stability is uncertain.

Algorithm time complexity

In algorithm analysis, the total number of statements executed T(n) is a function of problem size n, and then the change of T(n) with n is analyzed and the order of magnitude of T(n) is determined. The time complexity of the algorithm, that is, the time measure of the algorithm, is denoted as T(n)=O(f(n)). It means that with the increase of problem size N, the growth rate of algorithm execution time is the same as that of F (n), which is called the time complexity of the algorithm, or time complexity for short. Where f(n) is some function of the size n of the problem.

The commonly used time complexity takes up the order of time from smallest to largest

The O (1) < O (logn) < O (n) < O (nlogn) < O (n squared) < O (n) after < O (2 ^ n) < O (n!) < O(n^n)

photo

The time complexity of an algorithm has some common ratios to run time. See chart sources

The complexity of the 10 20 50 100 1000 10000 100000
O(1) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(log(n)) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(n) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O(n*log(n)) < 1s < 1s < 1s < 1s < 1s < 1s < 1s
O (n squared) < 1s < 1s < 1s < 1s < 1s 2 s 3-4 min
O (n) after < 1s < 1s < 1s < 1s 20 s 5 hours 231 days
O(2^n) < 1s < 1s 260 days hangs hangs hangs hangs
O(n!) < 1s hangs hangs hangs hangs hangs hangs
O(n^n) 3-4 min hangs hangs hangs hangs hangs hangs

Wikipedia’s explanation of algorithm stability

When equal elements are indistinguishable, such as integers, stability is not a problem. However, suppose the following pairs are to be sorted by their first digit.

(4, 1) (3, 1) (3, 7) (5, 6)Copy the code

In this case, it is possible to have two different results, one that maintains relative order for records with equal key values, and the other that does not:

(3, 1) (3, 7) (4, 1) to (5, 6) (keep order) (3, 7) (3, 1) (4, 1) to (5, 6) be changed (order)Copy the code

Want to see the stability of your browser’s sorting algorithm? Am I

How fast is which

Let’s test it out through this online site

What is the impact of different browser implementations

What are the effects of sorting algorithm instability

Here’s an example:

In the motor vehicle license plate auction system of a city, the final winning rule is as follows:

1. Reverse order by price;

2. The same price will be in positive order according to the bidding order (i.e. the time of price submission).

When sorting is done on the front end, the winning bidder displayed in a quicksort browser is likely to be incorrect.

The solution

Array.prototype.sort differences and workaround in different browsers

The general idea is to write a stable sorting function to maintain consistency across browsers.

Further reading

Javascript implementation of Quicksort

JS can be used to get all sorts of algorithms

7 common sorting algorithms – Visualization

Take a closer look at javascript’s sort method

Summary of JavaScript sorting algorithms

JS can be used to get all sorts of algorithms

Reference documentation

Talk about front-end sorting

Sorting algorithm

Summary of JavaScript sorting algorithms

Segmentfault.com/a/119000000…

www.iteye.com/topic/11383…

www.chongchonggou.com/g_41116884….

www.teakki.com/p/57dfbf44d…

www.cfei.net/archives/21… Bbs.it-home.org/thread-7191…

www.ctolib.com/topics-7479…

www.techug.com/post/sort-i…

Imweb. IO/topic / 565 cf…