Substream applied to unordered streams

Andrew Haley aph at
Tue Mar 19 02:54:49 PDT 2013

On 03/16/2013 08:52 PM, Brian Goetz wrote:
> I haven't yet determined whether we want to commit to stable sorting. 
> But I think we probably do not.  Stability is a relatively cheap 
> property to preserve in a sequential sort (which is why Arrays.sort is 
> spec'ed as stable), but a relatively expensive property to preserve in 
> an parallel sort, and this moves the balance of whether stability is 
> worth the cost.

Why?  Merge sorting is usually stable, and parallel sorting is Xsort
followed by a bunch of merges.  What is it about parallel sorting that
makes stability expensive?

I guess there's something I must be missing.  Stability is an
extremely useful property.


More information about the lambda-dev mailing list