Substream applied to unordered streams

[Doug Lea]

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.

-Doug