Does the JavaScript Array.sort() Method Use Stable Sort Algorithm?

Find out if Array.sort() uses the stable sort algorithm

Starting with ES10, the specification explicitly states that the Array.prototype.sort() method sorting algorithm must be stable (i.e. elements that compare equal must remain in their original order):

// ES10+
const ratings = [
  { name: 'foo', rating: 4 },
  { name: 'bar', rating: 2 },
  { name: 'baz', rating: 4 },
  { name: 'qux', rating: 3 },
];

ratings.sort((a, b) => a.rating - b.rating);

console.log(ratings);

This would sort the array of objects based on the comparison of numbers, producing the following result:

/* [
  { name: 'bar', rating: 2 },
  { name: 'qux', rating: 3 },
  { name: 'foo', rating: 4 }, // maintains original order (stable sorting)
  { name: 'baz', rating: 4 }, // maintains original order (stable sorting)
] */

Stable sort algorithm is supported in all modern browsers, and in Node.js 12.0.0+.

As you can see, the elements that compare equal retain their original order. In versions prior to ES10, however, the standard does not specify which sorting algorithm an implementation should use. Therefore, stable sorting cannot be guaranteed, and could result in equal values not retaining their original order, potentially producing the following result:

/* [
  { name: 'bar', rating: 2 },
  { name: 'qux', rating: 3 },
  { name: 'baz', rating: 4 }, // original order not maintained
  { name: 'foo', rating: 4 }, // original order not maintained
] */

To overcome this issue in versions prior to ES10, you could use a stable sorting algorithm (such as merge sort, etc.), or you could do the following to ensure that elements that are equal maintain their original order:

  1. Loop over all elements of the array and add a unique index to each element;
  2. Sort unequal elements using your desired sorting criteria, and;
  3. Sort items that compare equal by the unique index (as no two indexes will ever be equal).

For example, you can implement this for an array of objects in the following way:

function stableCompare(arr, sortByKey) {
  // 1: assign unique index to each element
  arr.forEach(function(el, i) {
    el.index = i;
  });

  arr.sort(function(a, b) {
    if (a[sortByKey] !== b[sortByKey]) {
      // 2: sort by comparing object values
      return a[sortByKey] - b[sortByKey];
    }

    // 3: sort by comparing unique index
    return a.index - b.index;
  });

  return arr;
}

const ratings = [
  { name: 'foo', rating: 4 },
  { name: 'bar', rating: 2 },
  { name: 'baz', rating: 4 },
  { name: 'qux', rating: 3 },
];

console.log(stableCompare(ratings, 'rating'));

This would produce the following output:

/* [
  { name: 'bar', rating: 2, index: 1 },
  { name: 'qux', rating: 3, index: 3 },
  { name: 'foo', rating: 4, index: 0 },
  { name: 'baz', rating: 4, index: 2 },
] */

Remember to choose a different name for the index key if your objects already have an existing key with the same name.


Hope you found this post useful. It was published . Please show your love and support by sharing this post.