Array#sort() implementations not interoperable

Kevin Gadd kevin.gadd at gmail.com
Thu Jun 13 16:42:45 PDT 2013


I'll state it again since I guess maybe the third time is the charm:

When I said 'always stable' or 'always unstable' i was referring to which
implementation the browser uses, not what the sort actually does. There's
nothing beneficial about the fact that an unstable sort happens to
rearrange elements. My point is that explicitly forbidding Array.sort from
conditionally switching between sort implementations (or at least from
switching between implementations with observable differences) is
beneficial to users. Let's not be ridiculous here.

-kg


On Thu, Jun 13, 2013 at 3:53 PM, felix <felix8a at gmail.com> wrote:

> 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
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130613/8d5c2c45/attachment.html>


More information about the es-discuss mailing list