Array.sort Sorting Stability in Different Browsers

Question

What is the stability of Array.sort in different browsers. I know that the ECMA Script specification does not specify which algorithm to use, nor does it specify whether the sort should be stable.

I've found this information for Firefox at https://developer.mozilla.org/en/Core_JavaScript_1.5_Reference/Global_Objects/Array/sort which specifies that firefox uses a stable sort.

Does anyone know about IE 6/7/8, Chrome, Safari?

Answer 1

If you are looking for a list of browsers where you should utilize a non native sorting algorithm, my suggestion is don't.

Instead do a sort sanity check when the script loads and make your decision from that.

As the spec doesn't require a particular behavior in that regard, it is not immune to later change, even within the same browser line.

You could submit a patch to http://www.browserscope.org/ to include such tests in their suite. But again, feature detection is superior to browser detection.

Answer 2

I can't help you much (haven't touched JS for many years) but share a trick I use in C/C++ I routinely use 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. This are indexes into the original array. We are going to sort the second array. Make a custom compare function. It will get the two elements from the second array: use them as indexes into the original arrays and compare the elements. If elements happen to be equal, then compare their indexes to make the order stable. After the sort(), the second array would contain indexes which you can use to access the elements of original array in stable sorted order.

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.

Answer 3

Simple test case (ignore the heading, second set of numbers should be sequential if the engine's sort is stable).

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 <= 5 (i.e., all versions to date): unstable
• Opera < 10: unstable
• Opera >= 10: stable
• Safari 4: stable

All tests on Windows.

See also:

• Fast stable sorting algorithm implementation in javascript