Menu
I know that the ECMA Script specification does not specify which algorithm to use for sorting arrays, nor does it specify whether the sort should be stable.
I've found this information for Firefox which specifies that firefox uses a stable sort.
Does anyone know about IE 6/7/8, Chrome and Safari?
517
Several common sorting algorithms are stable by nature, such as Merge Sort, Timsort, Counting Sort, Insertion Sort, and Bubble Sort. Others such as Quicksort, Heapsort and Selection Sort are unstable. We can modify unstable sorting algorithms to be stable.
Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist).
All major JavaScript engines now implement a stable Array#sort . It's just one less thing to worry about as a JavaScript developer. Nice! (Oh, and we did the same thing for TypedArray s: that sort is now stable as well.)
As of ES2019, sort is required to be stable. In ECMAScript 1st edition through ES2018, it was allowed to be unstable.
Simple test case (ignore the heading, second set of numbers should be sequential if the engine's sort is stable). Note: This test case doesn't work for some versions of Chrome (technically, of V8) that switched sorting algorithms based on the size of the array, using a stable sort for small arrays but an unstable one for larger arrays. (Details.) See the end of the question for a modified version that makes the array large enough to trigger the behavior.
IE's sort has been stable as long as I've ever used it (so IE6). Checking again in IE8 and it appears to still be the case.
And although that Mozilla page you link to says Firefox's sort is stable, I definitely say this was not always the case prior to (and including) Firefox 2.0.
Some cursory results:
All tests on Windows.
See also: Fast stable sorting algorithm implementation in javascript
This test case (modified from here) will demonstrate the problem in V8 (for instance, Node v6, Chrome < v70) by ensuring the array has enough entries to pick the "more efficient" sort method; this is written with very old JavaScript engines in mind, so without modern features:
function Pair(_x, _y) { this.x = _x; this.y = _y; } function pairSort(a, b) { return a.x - b.x; } var y = 0; var check = []; while (check.length < 100) { check.push(new Pair(Math.floor(Math.random() * 3) + 1, ++y)); } check.sort(pairSort); var min = {}; var issues = 0; for (var i = 0; i < check.length; ++i) { var entry = check[i]; var found = min[entry.x]; if (found) { if (found.y > entry.y) { console.log("Unstable at " + found.i + ": " + found.y + " > " + entry.y); ++issues; } } else { min[entry.x] = {x: entry.x, y: entry.y, i: i}; } } if (!issues) { console.log("Sort appears to be stable"); }If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
