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: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.