sorting and stability
dl at cs.oswego.edu
Mon Mar 25 16:30:17 PDT 2013
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.
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?
More information about the lambda-libs-spec-experts