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

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?

Solution 1:

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

Solution 2:

I'd like to share a trick I routinely use in C/C++ for qsort().

JS' sort() allows to specify a compare function. Create second array of the same length and fill it with increasing numbers from 0.

function stableSorted(array, compareFunction) {
  compareFunction = compareFunction || defaultCompare;
  var indicies = new Array(array.length);
  for (var i = 0; i < indicies.length; i++)
    indicies[i] = i;

This are indexes into the original array. We are going to sort the second array. Make a custom compare function.

  indicies.sort(function(a, b)) {

It will get the two elements from the second array: use them as indexes into the original arrays and compare the elements.

    var aValue = array[a], bValue = array[b];
    var order = compareFunction(a, b);
    if (order != 0)
      return order;

If elements happen to be equal, then compare their indexes to make the order stable.

   if (a < b)
     return -1;
   else
     return 1;
  });

After the sort(), the second array would contain indexes which you can use to access the elements of original array in stable sorted order.

  var sorted = new Array(array.length);
  for (var i = 0; i < sorted.length; i++)
    sorted[i] = array[indicies[i]];
  return sorted;
}

// The default comparison logic used by Array.sort(), if compareFunction is not provided:
function defaultCompare(a, b) {
  a = String(a);
  b = String(b);
  if (a < b) return -1;
  else if (a > b) return 1;
  else return 0;
}

In general, stable sort algorithms are only maturing and still require more extra memory compared to the good ol' qsort. I guess that's why very few specs mandate stable sort.