why is List.sort unstable?

I don't see any good reason for this to be an unstable sort.

It's that way right now because a merge sort is used, and to split the initial list in two, it doesn't chop the list in the middle; rather, it walks through the list, alternating elements as it goes ("one for you, one for me" style).  Not a bad idea in general--it prevents having to run to the end of the list to measure its length.

It could probably be made stable if the merge were modified to alternate between each list in the same way.

But this isn't the most efficient way to do it since the lists are immutable (if they were mutable, then this split could be a quick re-aiming of pointers).  Better would be to stuff the whole thing into an ArrayBuffer, sort the ArrayBuffer using mergesort, and then convert back to a list at the end.

  --Rex

On Tue, May 11, 2010 at 4:13 PM, Eric Bowman <ebowman@boboco.ie> wrote:

More than once I've found myself scratching my head wondering why a
program behaves slightly differently with each execution.  Rewriting it
to use Sorting.stableSort instead fixes the problem.  Kind of annoying,
ultimately -- unless there is a good reason for it, it seems like it
would be a lot nicer if List.sort were stable (since it's so convenient).

Is there a good reason?

Thanks,
Eric

--
Eric Bowman
Boboco Ltd
ebowman@boboco.ie
http://www.boboco.ie/ebowman/pubkey.pgp
+35318394189/+353872801532

Hi Eric,

On Tue, May 11, 2010 at 9:13 PM, Eric Bowman wrote:
> Kind of annoying,
> ultimately -- unless there is a good reason for it, it seems like it
> would be a lot nicer if List.sort were stable (since it's so convenient).

In 2.8.0, List.sort is deprecated:

@deprecated("use `sortWith' instead")

Best,
Ismael

Or sorted.

On Tue, May 11, 2010 at 5:39 PM, Ismael Juma <mlists@juma.me.uk> wrote:

Hi Eric,

On Tue, May 11, 2010 at 9:13 PM, Eric Bowman <ebowman@boboco.ie> wrote:
> Kind of annoying,
> ultimately -- unless there is a good reason for it, it seems like it
> would be a lot nicer if List.sort were stable (since it's so convenient).

In 2.8.0, List.sort is deprecated:

@deprecated("use `sortWith' instead")

Best,
Ismael

--
Daniel C. Sobral

I travel to the future all the time.