Array#sort() implementations not interoperable

felix felix8a at gmail.com
Thu Jun 13 15:53:52 PDT 2013


Always-unstable is trivial: use a stable sort, and the first time you
encounter two elements that compare equal, swap them. The problem with
that is it isn't necessarily detectably unstable. The two elements you
swap might be equal in all ways. To be detectably unstable, you need
the sort function to know when two elements that compare equal are not
otherwise equal, so you have to pass it a second comparison function,
and if you can do that why are you bothering with an unstable sort in
the first place? I think I'm confused about the point of "always
unstable".

An alternate interpretation of "always unstable" is for sort to throw
an error anytime it encounters two elements that compare equal. Which
is pretty annoyingly useless. You might as well just use a stable sort
all the time.

On Thu, Jun 13, 2013 at 3:10 PM, Sean Silva <silvas at purdue.edu> wrote:
> On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd <kevin.gadd at gmail.com> wrote:
>>
>> I don't understand why you would intentionally sidetrack a discussion
>> about a simple problem with academic details.
>
>
> He brings up a very real point, which is that you can't realistically have
> an "always unstable" sort. If I understand you correctly, what you want by
> an "always unstable" sort is that you want developers to "get bitten" in
> testing due to instability, even for small test cases, so that the issue is
> caught earlier. The problem with that desire is that there are no sorting
> algorithms AFAIK that guarantee that they will *always* rearrange
> equal-sorting elements (i.e., "always unstable"): even a pure recursive
> quicksort (no insertion-sort base case) will sometimes not rearrange
> equal-sorting elements (i.e., seem stable).
>
> If I understand your desire correctly, then what you're asking for by
> "always unstable" is to require that if an implementation's sorting
> algorithm *might* rearrange equal-sorting elements, then it must *always* go
> out of its way to ensure that if equal-sorting elements are present, then it
> does not preserve their order; I haven't looked in detail at what this would
> mean from an implementation standpoint, but I'm pretty sure that it is
> unrealistic.
>
> -- Sean Silva
>
> _______________________________________________
> es-discuss mailing list
> es-discuss at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>


More information about the es-discuss mailing list