Fast stable sorting algorithm implementation in javascript

Question

I'm looking to sort an array of about 200-300 objects, sorting on a specific key and a given order (asc/desc). The order of results must be consistent and stable.

What would be the best algorithm to use, and could you provide an example of it's implementation in javascript?

Thanks!

Solution 1

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

Solution 2

Since you are looking for something stable, the merge sort should do.

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

The code can be found at the above website:

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

EDIT:

According to this post, it looks like Array.Sort in some implementations uses a merge sort.

Solution 3

Somewhat shorter version of the same thing using ES2017 features like arrow functions and destructuring:

Function

var stableSort = (arr, compare) => arr
  .map((item, index) => ({item, index}))
  .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
  .map(({item}) => item)

It accepts input array and compare function:

stableSort([5,6,3,2,1], (a, b) => a - b)

It also returns new array instead of making in-place sort like the built-in Array.sort() function.

Test

If we take the following input array, initially sorted by weight:

// sorted by weight
var input = [
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 }
]

Then sort it by height using stableSort:

stableSort(input, (a, b) => a.height - b.height)

Results in:

// Items with the same height are still sorted by weight 
// which means they preserved their relative order.
var stable = [
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 }
]

However sorting the same input array using the built-in Array.sort() (in Chrome/NodeJS):

input.sort((a, b) => a.height - b.height)

Returns:

var unstable = [
  { height: 70, weight: 140 },
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 100 },
  { height: 100, weight: 80 },
  { height: 100, weight: 135 },
  { height: 100, weight: 120 },
  { height: 110, weight: 115 }
]

Resources

• Wikipedia
• MDN
• JSFiddle

Update

Array.prototype.sort is now stable in V8 v7.0 / Chrome 70!

Previously, V8 used an unstable QuickSort for arrays with more than 10 elements. Now, we use the stable TimSort algorithm.

source

Solution 4

I know that this question has been answered for some time, but I happen to have a good stable merge sort implementation for Array and jQuery in my clipboard, so I'll share it in the hopes that some future searchers might find it useful.

It allows you to specify your own comparison function just like the normal Array.sort implementation.

Implementation

// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn't pollute the global
//       namespace, but we don't put it in $(document).ready, since it's
//       not dependent on the DOM
(function() {

  // expose to Array and jQuery
  Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

  function mergeSort(compare) {

    var length = this.length,
        middle = Math.floor(length / 2);

    if (!compare) {
      compare = function(left, right) {
        if (left < right)
          return -1;
        if (left == right)
          return 0;
        else
          return 1;
      };
    }

    if (length < 2)
      return this;

    return merge(
      this.slice(0, middle).mergeSort(compare),
      this.slice(middle, length).mergeSort(compare),
      compare
    );
  }

  function merge(left, right, compare) {

    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        if (compare(left[0], right[0]) <= 0) {
          result.push(left[0]);
          left = left.slice(1);
        }
        else {
          result.push(right[0]);
          right = right.slice(1);
        }
      }
      else if (left.length > 0) {
        result.push(left[0]);
        left = left.slice(1);
      }
      else if (right.length > 0) {
        result.push(right[0]);
        right = right.slice(1);
      }
    }
    return result;
  }
})();

Example Usage

var sorted = [
  'Finger',
  'Sandwich',
  'sandwich',
  '5 pork rinds',
  'a guy named Steve',
  'some noodles',
  'mops and brooms',
  'Potato Chip Brand® chips'
].mergeSort(function(left, right) {
  lval = left.toLowerCase();
  rval = right.toLowerCase();

  console.log(lval, rval);
  if (lval < rval)
    return -1;
  else if (lval == rval)
    return 0;
  else
    return 1;
});

sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];

Solution 5

You can use the following function to perform a stable sort regardless of the native implementation, based on the assertion made in this answer.

Do note that as of ECMAScript 2019, the specification requires that the builtin sort() method perform a stable sort. With that in mind, an explicit stable sort function like the one below is still relevant if you are required to support older browsers that are not specification compliant.

// ECMAScript 5 implementation
function stableSort(array, compareFunction) {
  'use strict';

  var length = array.length;
  var indices = new Uint32Array(length);
  var i;
  var slice;

  // reference values by indices
  for (i = 0; i < length; ++i) {
    indices[i] = i;
  }

  // sort with fallback based on indices
  indices.sort(function stableCompareFunction(compareFunction, a, b) {
    var order = Number(compareFunction(this[a], this[b]));
    return order || a - b;
  }.bind(array, compareFunction));

  slice = array.slice();

  // re-order original array to stable sorted values
  for (i = 0; i < length; ++i) {
    array[i] = slice[indices[i]];
  }

  return array;
}

// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)));

const alwaysEqual = () => 0;
const isUnmoved = (value, index) => value === array[index];

// not guaranteed to be stable before ES2019
console.log(
  'sort() stable?',
  array.slice().sort(alwaysEqual).every(isUnmoved)
);
// guaranteed to be stable
console.log(
  'stableSort() stable?',
  stableSort(array.slice(), alwaysEqual).every(isUnmoved)
);

// performance using realistic scenario with unsorted big data
function time(arraySlice, algorithm, compare) {
  var start;
  var stop;

  start = performance.now();
  algorithm(arraySlice, compare);
  stop = performance.now();

  return stop - start;
}

const ascending = (a, b) => a - b;

const msSort = time(array.slice(), (array, compare) => array.sort(compare), ascending);
const msStableSort = time(array.slice(), (array, compare) => stableSort(array, compare), ascending);

console.log('sort()', msSort.toFixed(3), 'ms');
console.log('stableSort()', msStableSort.toFixed(3), 'ms');
console.log('sort() / stableSort()', (100 * msSort / msStableSort).toFixed(3) + '%');

Running the performance tests implemented above, stableSort() appears to run at about 72% of the speed of sort() on version 88 of Google Chrome and Microsoft Edge.

Using .bind() on the inline function within stableSort() used to boost relative performance significantly by avoiding unneeded scoped references on each call.

In practice, this no longer makes a difference since modern engines automatically perform this optimization now, but it is left in the implementation anyway in order to continue improving performance in older browsers which don't ship with this optimization.

View more solutions

Comments

[Nosredna]

Since at least Chrome's array sort doesn't seem to be stable, relying on the built-in array sort is not an option for you.

[William Casarin]

To summarize: I went with a hand rolled merge sort due to Array.sort stability inconsistencies between modern browsers (mainly chrome not implementing a stable sort at the time of this comment). Thanks everyone for your help!

[mowwwalker]

What do we mean by "stable" sort?

[Kornelije Petak]

@mowwwalker Stable sort is a sort in which all of the items with the same sorting value are left in the same order as in the original collection. en.wikipedia.org/wiki/Sorting_algorithm#Stability

[will]

To answer "what is the best algorithm to use" we need to know if there is any underlying structure to your data. A lot of the answers below just talk about using merge sort, or quick sort, in reality it depends on the data. It's not a simple problem to just answer i wouldn't say. Google a few sorting algorithms and read about them to see what i mean. TimSort and Radix Sort are two good examples i'd reccomend reading about.

[Renganathan M G]

Please refer the following link. khan4019.github.io/front-end-Interview-Questions/sort.html

[jchook]

You can use lodash's _.sortBy() which is stable.

[Berkyjay]

With the exception of Internet Explorer, Array.sort is stable in all browsers as of November 2018 as mandated by the standard. Browser compatibility

[Mike Dunlavey]

++ Merge sort is my favorite. It's simple and stable with no bad worst cases.

[Domi]

A few things to be said: 1. Counting sort only works well in a dense number space. (Try sorting the array [1, 2e9, 1e9]) 2. Don't write for loops as while loops. 3. Don't randomly add things to the Math namespace. 4. You might want to consider making friends with semicolons.

[Eric]

Note this is at odds with the native sort, which works in place, meaning this cannot just be dropped in.

[davidkonrad]

Maybe stable, but this method is about 20 times slower than native array.sort, see test here for both strings and integers -> jsfiddle.net/QC64j

[Justin Force]

Of course it's slower than native sort—it's not native. That's impossible. It's also true that it doesn't do an in place sort. That's also impossible (best case you create a copy then overwrite the original). Besides, returning a sorted copy is more JavaScript-y despite JavaScript's own native sort behavior. The function is also called mergeSort and not sort, so it's not intended as a drop in replacement. Sometimes you just need a stable merge sort, e.g. when sorting tables by column.

[ahitt6345]

Wrong, Node's Native sort is written in javascript. Its entirely possible for an algorithm programmed in javascript to out-speed the native sort. I built a sorting algorithm entirely in javascript(a type of adaptive merge sort) that Kremes/creams/Kreams The native quicksort in node. The point of this comment is to show that native does not matter in the case of javascript because the sorting algorithm is written in javascript and not in some higher language such as c++. Proof is here: github.com/nodejs/node/blob/master/deps/v8/src/js/array.js

[ahitt6345]

The link to the website is down :(

[kemiller2002]

found a new website for the example.

[Justin Force]

@ahitt6345 So we know that's true for V8 and Node. The implementation of .sort() is not guaranteed to be in JavaScript. The whole point here is that ECMAScript's sort is not guaranteed to be stable. Any given implementation of JavaScript may have a stable sort, but since it's not guaranteed by the spec you shouldn't rely on it. Similarly, the spec doesn't stipulate that .sort() be implemented in JavaScript. And some minor nitpicks: C++ is a lower level language than JavaScript; and your tone sucks.

[4esn0k]

Are your benchmark correct? Seems, your "stableSort" does not modify input array, other sorts - do, and as you did not recreate "arr" during "setup", other sorts sort already sorted arrays....

[4esn0k]

@JustinForce if Array#slice works in O(n) time your merge will work in O(n*n).

[4esn0k]

Note: Array#shift may workn in O(n) time and so your merge in O(n*n).

[MKPS]

Also, in case where array has duplicate values, it will run forever. For example, array [3, 1, 3] hashes to [undefined, 1, undefined, 3]. We get two non-undefined values, while algorithm expects there to be three of them.

[Mohammad Kermani]

Could you please provide the answer here instead of posting and linking to your blog! Thanks

[goat]

@4esn0k did you read wrong? I said my stableSort func was NOT fast.

[4esn0k]

@gota, ah, pardon me

[Patrick Roberts]

For anyone who wants an in-place, drop-in solution that's much faster than this implementation, check out my answer.

[martian]

Not stable for primitive types or duplicate elements in array. jQuery.expando.split( "" ).sort( ( a, b ) => 0 ).join( "" ) === jQuery.expando

[Samuel Liew]

A link to a solution is welcome, but please ensure your answer is useful without it: add context around the link so your fellow users will have some idea what it is and why it’s there, then quote the most relevant part of the page you're linking to in case the target page is unavailable. Answers that are little more than a link may be deleted.

[William Casarin]

@Vjeux since this is getting to be a popular, do you mind pasting the relevant code into this answer? It would help a lot! thanks!

[lhermann]

The stableSort function is a really great solution!

[Berkyjay]

Array.sort is stable in all browsers as of November 2018 as mandated by the standard. Browser compatibility