Array#sort() implementations not interoperable

Sean Silva silvas at purdue.edu
Thu Jun 13 15:10:49 PDT 2013


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


More information about the es-discuss mailing list