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)

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.

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