Substream applied to unordered streams
aph at redhat.com
Wed Mar 20 03:23:43 PDT 2013
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.
More information about the lambda-dev