17

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:
Community
  • 1
  • 1
forivall
  • 9,504
  • 2
  • 33
  • 58
  • 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. – apsillers May 15 '13 at 20:43
  • 2
    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. – frozenkoi May 15 '13 at 20:47
  • 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]`. – apsillers May 15 '13 at 20:47

4 Answers4

5

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.

Sara
  • 499
  • 3
  • 8
1

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

MarZab
  • 2,543
  • 21
  • 28
  • 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 – Steven Lu May 15 '13 at 21:04
1

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.

Jason
  • 3,021
  • 1
  • 23
  • 25
0

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?

Thomas W
  • 13,940
  • 4
  • 58
  • 76