What Is the Stability of the Array.Sort() Method in Different Browsers

What is the stability of the Array.sort() method in different browsers?

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:

• IE6+: stable
• Firefox < 3: unstable
• Firefox >= 3: stable
• Chrome < 70: unstable
• Chrome >= 70: stable
• Opera < 10: unstable
• Opera >= 10: stable
• Safari 4: stable
• Edge: unstable for long arrays (>512 elements)

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");}

Array.prototype.sort(compareFn) works different in browsers?

I get unexpected behaviour in Chrome. Anybody know what happens?

Actually, this is not unexpected. It appears that your Firefox browser version implements stable sorting, whereas your Chrome browser version does not. Browsers are not required to adopt a stable sorting algorithm (and may choose performance over stability).

A stable sorting algorithm returns equal list items in the same order as they appear originally, whereas an unstable sorting algorithm does not.

Stable and unstable sorting

Consider the following example, where a list of 11 men is sorted according to their age. The sorting algorithm sees 9 men of the same age (45 years old), one younger (39 years old), and one older (52 years old). After sorting, the youngest one (Mike) appears first in the list, then the 9 of the same age may appear in any order, and then the oldest one (Liam) at the end.

console.log([    {name: 'John', age: 45},    {name: 'Pete', age: 45},    {name: 'Matt', age: 45},    {name: 'Liam', age: 52},    {name: 'Jack', age: 45},    {name: 'Will', age: 45},    {name: 'Zach', age: 45},    {name: 'Josh', age: 45},    {name: 'Ryan', age: 45},    {name: 'Mike', age: 39},    {name: 'Luke', age: 45}  ].sort(function(a, b){    // sort by ascending age    return a.age - b.age;  }).map(function(i){    // get a sorted list of names    return i.name;  }).join(', '));

Why is the Array.sort() method in my Javascript program unstable?

Because JS' sorting is typically unstable. From §22.1.3.24 of the spec:

The elements of this array are sorted. The sort is not necessarily stable (that is, elements that compare equal do not necessarily remain in their original order).

Your teams are created with identical properties except their name, so the line actually performing the sort is:

return teams.indexOf(a)-teams.indexOf(b);

Because you're calling indexOf, it searches for the item (and its index) each repetition of the sort. Sorting mutates the array (from MDN: it "sorts the elements of an array in place and returns the array").

You are searching for the item within the same array you are sorting, so the index may change on each iteration. Done correctly (relatively speaking), you could produce a never-ending sort with that.

For example:

const data = [1, 3, 2, 4];let reps = 0;
data.sort((a, b) => {  console.log(data);    const ia = data.indexOf(a), ib = data.indexOf(b);  if (ia === ib || reps > 50) {    return 0;  } else if (ia < ib) {    return 1;  } else if (ib < ia) {    return -1;  }    });

How can I ensure a stable array.sort() order, javascript

First of all, like Array#sort and other sort implementations:

The sort is not necessarily stable.

To maintain a stable sort, you could use a unique value, like an index as last sort value in the chain of sorting criteria, like

function asc(key) {
    return function (a, b) {
        return a[key] - b[key] || a.id - b.id;
    };
}

array.sort(asc('value'));

Fast stable sorting algorithm implementation in javascript

It is possible to get a stable sorting from a non-stable sort function.

Before sorting you get the position of all the elements.
In your sort condition, if both elements are equal, then you sort by the position.

Tada! You've got a stable sort.

I've written an article about it on my blog if you want to know more about this technique and how to implement it: http://blog.vjeux.com/2010/javascript/javascript-sorting-table.html

will Array.sort() preserve the order of the array, where possible?

What you're looking for is whether or not the algorithm is "stable". It is known that Firefox's is not, while IE's is. The javascript standard doesn't require a stable sorting algorithm.

Edit: Firefox 3+ has a stable sort. Please see http://www.hedgerwow.com/360/dhtml/js_array_stable_sort.html

---

Related Topics