[concurrency-interest] Using TimSort merges for ParallelArray.sort()

Doug Lea dl at cs.oswego.edu
Sun Sep 18 08:09:55 EDT 2011


On 09/17/11 20:27, Wolfgang Hoschek wrote:
> We're considering to use the parallel merge sort in the ParallelArray class
> of the extra166y package for stable sorting.

There's an intrinsic mismatch between stable-sort guarantees
(i.e., that ties are kept in original sequential order) and
parallelism. It's possible to get some parallelism here, but
the added sequential constraint reduces potential speedups.
I think that it is still an open question whether it is
usually worthwhile, since stable sorts are often desired
when data are already mostly sorted anyway, in which
case a sequential application of TimSort will likely
be about as fast as anything else you can do.

>
> I'm wondering if the ideas in TimSort could be successfully applied to the
> merge phase of the ParallelArray sort algorithm as well.

An additional small snag here is that TimSort internally
allocates small merge space arrays. But a parallel sort must
bulk-allocate the entire merge array anyway, which should
ideally be used in these calls, but won't be unless/until
TimSort has an internal API that allows callers to provide
them.

-Doug



More information about the Concurrency-interest mailing list