Is there a black box method to detect if a sorting algorithm is stable?

Question

In JavaScript (somewhat applicable elsewhere), where you don't know what target implementation your code is running on, is there a way to feature detect if the underlying sorting algorithm (of Array.sort) is stable or not, knowing only that it follows the specification?

I could find 2 tests in webkit (1) (2), but how reliable are those tests? (Could this check be done with a PCP?) I'm looking for a solution that would be mathematically sound.

This is a tricky problem, since a more advanced sorting algorithm can change subalgorithms depending on the length of the source array (like Timsort). I've been confused since every test I've run has shown Google Chrome's sort to be stable, but all documentation I've seen has said that it's unstable (the source will tell you why).

(Typically, I use this strategy to make my sorts stable; it has a small but sometimes noticable performance impact)

Source code for sorting in various implementations:

• Google Chrome/ium - V8
• Safari - JSC
• Firefox - *Monkey (2) (3)

Gentle

You can only make such a determination probabilistically: for instance, I can define a sort algorithm S that takes input I. Normally, S farms out the actual sorting work to some stable sortalgorithm T, but when I equals some special value I', it uses an non-stable sort U instead. You'll never prove that S is non-stable unless you luck out and happen to pass I' as input. More realistically, perhaps S uses stable sorts unless I is very long. Again, you'll only observe non-stable sorts if you test on suitably long inputs. – Langevin

If the spec says that it's not stable, that doesn't mean that you can expect the items to swap order when you sort the array, but rather that you can't rely on it; there are no promises. That the (current) implementation happens to be stable does not mean that it will always be, or for all the platforms chrome runs on. – Hasen

I agree with @MarZab that this is a halting-problem issue. You might see some more attention if you tag it [computer-science] and/or [computer-science-theory]. – Langevin

Answer 1

Black-box testing can not be used to determine that a program satisfies any criterion unless you can test all possible inputs relevant to the criterion. A black box is free to simply have a lookup table that maps inputs to outputs (see Pentium FDIV bug for a real-world lookup table bug) so you cannot be sure that your tests preclude the possibility of some other input triggering a violation.

Quinze

Answer 2

Mathematically sound, eh? That would require every path in the algorithm to be proved stable - and every combination of them. For any possible data.

Sure algorithms like that exist - but they were most probably made to fit that requirement. So if it is, it probably says it is somewhere.

As for a test to prove something like that, that probably falls under similar issues as a Halting problem.

http://en.wikipedia.org/wiki/Halting_problem

Shanta

Not sure if necessary to invoke Halting problem, but it should be clear that superexponential search is necessary to cover all possibilities for a given input size – Boles

Answer 3

Why risk it? For most reasonable data sets, a javascript implementation of merge sort should be fast enough. Pick up a couple and benchmark them and use the best one.

Solder

If someone is asking this question, they are likely in a situation where having a native stable sort is an optimization they have determined is worth it. – Neukam

Answer 4

Run a small internal test, to check? You could use the "playing-cards by rank, then by suit" example from Wikipedia to check for stability.

See: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

I don't know how many cards you need to check stability -- perhaps 5 or so?

Swaim

Answer 5

To answer your question, there's no black box test that is immune to false positives.

As of ES 2019, the sort method is stable by specification. However, there seems to have been an oversight in the spec, as no accommodation has been made for checking if sort is stable at runtime, which means you have to assume that it isn't, short of a UA sniff. This defeats the purpose of providing a stable sort.

If you are ok with a UA sniff, you can simplify things by just checking for version 100 or higher of Chrome, Firefox, and Edge, or version 10 or higher of Safari. This is not inclusive of all browser versions that include a stable sort, but is relatively simple and will allow you to take advantage of native stable sort for the vast majority of users.

/(Chrome|Firefox|Edg)\/(\d{3,})|Version\/(\d{2,})\.\d+ Safari\//.test(navigator.userAgent)

Neukam

Answer 6

Even if your black-box testing says that the sort is stable, so what? All that tells you is that the current implementation of the sorting algorithm is probably stable. Unless the specification states that it is stable, the next version of the sort can be a different implementation.

For the longest time, the standard Python implementation of dict used an implementation in which iteration order was the same as insertion order. But until this fact was put into the specification, the implementation could change.

Kelleekelleher