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

Wolfgang Hoschek wolfgang.hoschek at mac.com
Sat Sep 17 20:27:12 EDT 2011


We're considering to use the parallel merge sort in the ParallelArray class of the extra166y package for stable sorting.

However, I recently learned that Java 7 ships with TimSort, an optimized sequential adaptive merge sort that includes clever optimizations for partially ordered data in the merge phase, which is often a common case in practise. Here are some numbers:

http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-June/001933.html

I'm wondering if the ideas in TimSort could be successfully applied to the merge phase of the ParallelArray sort algorithm as well. And I'm wondering to what extent the parallel implementation can remain competitive with the sequential Java 7 sort for partially ordered data. With, say, 8 cores, partially ordered data and relatively expensive comparison functions.

Are there any plans to explore refining the algorithm before the release of extra166y?

P.S. The Java 7 TimSort was ported from Python for use in Android and contributed to Java by Josh Bloch @ Google, who is also the original author of the sort code in Java prior to JDK 7. 

References:
http://bugs.python.org/file4451/timsort.txt
http://en.wikipedia.org/wiki/Timsort
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6804124
http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-June/001937.html
http://hg.openjdk.java.net/jdk7/jdk7/jdk/raw-file/bfd7abda8f79/src/share/classes/java/util/TimSort.java

-Wolfgang Hoschek


More information about the Concurrency-interest mailing list