Substream applied to unordered streams

[Andrew Haley]

On 03/19/2013 11:19 AM, Doug Lea wrote:
> On 03/19/13 06:47, Paul Sandoz wrote:
> 
>>> 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?
> 
> Intuition: Suppose the array is split for independent parallel
> sorts in the middles runs with tied keys. If so, subsorts cannot
> necessarily be merged as soon as they are ready. There are ways to still
> cope, but they add cost. And the question then becomes whether
> the cost makes sense to impose given that you can always get
> a stable non-parallel sort if you need stability.

I see.  I suppose that I'd always prefer stability, given how annoying
unstable sorts are in many applications.

Andrew.