Is Javascript Array.sort() Stable?

I don’t mean “stable” as in “does it crash all the time”. Javascript’s implementations are (hopefully) more reliable than that. I mean stable in the algorithmic sense: does it preserve the order of otherwise “equal” items? Consider the following test case:

What gives? Well, if you’re getting one of the last three results, then you’re probably using Google Chrome, or maybe one of an assortment of browsers that does not implement Array.sort() as a “stable” algorithm.

Why, you ask? Well, nowhere in the ES7 specification does it say whether the sort needs to be stable or not. In fact, it tries to be super abstract, allowing as much of the sort to be “implementation defined” as possible. This has resulted in different JS engines (across different browsers) taking different routes to implementing this spec, leading to inconsistent sort stability behavior.

But I need Javascript to have a stable sort!

That’s too bad. There is no stable sort in the standard library. You’re going to either need to use a 3rd party library, or implement it yourself.

For a 3rd party library, I heartily recommend Lodash, which has great browser-agnostic utility functions for doing a variety of tasks, with a focus on functional programming. In particular, its Collection.sortBy() is stable!

If, for some reason, you prefer the classic JS sort() semantics (in-place, using a comparator instead of a “key” access), or if you are allergic to using 3rd party libraries, then you could easily implement that yourself by wrapping around Javascript’s default sort and adding your new function to the Array prototype:

If you’re looking for a type-safe Typescript “shim”, I got that too.

Yeah, it’s terrible. You could write your own sort implementation that’s stable from the get-go and avoids some of this mess! Try merge sort! It may be slower than JS’s built-in sort, though, given that the latter is likely implemented in the JS engine itself (in C/C++ bytecode).

Hopefully this little rant will have saved you a headache about your data not sorting itself right. If not, well… this probably belongs in the bottom book, not the top one: