sorting and stability

Joe Bowbeer joe.bowbeer at
Mon Mar 25 18:31:51 PDT 2013

sequential streams should be stable in all cases?

This is principle of least surprise.
On Mar 25, 2013 7:30 PM, "Doug Lea" <dl at> wrote:

> Prodded by a lambda-dev post, I've been looking more
> carefully into stability guarantees for Stream.sorted().
> It struck me that if the stream is ORDERED, then people
> have a reasonable expectation that the sort will be stable.
> Else not.
> Agreed?
> Algorithmically, the cost of this might on average be zero.
> Even though it does add cost in general, it can be made
> immeasurably small when there are no duplicate keys, and
> as fast as any other strategy when there are duplicates.
> I've done some preliminary versions of this that look
> pretty good. Barely-working hacks are already faster than the
> existing sorts in there now (ArraysParallelSortHelpers)
> that were based on my ParallelArray versions.
> But serious versions are not very close to being ready.
> Do we want to solidify specs anyway?
> -Doug
-------------- next part --------------
An HTML attachment was scrubbed...

More information about the lambda-libs-spec-experts mailing list