No generic version of DualPivotQuickSort

Doug Lea dl at
Tue Jan 27 12:18:38 UTC 2015

On 01/26/2015 03:54 PM, Buis, Paul wrote:
> The java.util.DualPivotQuicksort class implements sort() methods for the
> primitive types, has no methods that deal with generic arrays with methods
> like
> static <T extends Comparable<? super T>> void sort(T[] array, int iStart, int
> iEnd)
> Similarly, it contains no methods for Comparator-based sorting of generic
> arrays. Might it make sense to add such methods to DualPivotQucksort? The
> Arrays.sort() methods for generic arrays use TimSort which is likely to be
> slower. TimSort is stable and DualPivotQuickSort is not. Might it make sense
> to allow the user to pick a stable or an unstable version of a generic
> Arrays.sort() and use TimSort when stability is desired and
> DualPivotQuicksort when it is not?

This was considered, including when introducing parallelSort
for which ensuring stability requires a bunch of precautions.
But after putting these into place, there was little or no
benefit over non-stable forms for parallel case (which requires
allocating a workspace of size N anyway.) And for the non-parallel
case, TimSort does not do very much allocation, and is faster
for the majority of cases seen in practice. (There is a big
suite of test cases around, including I think some in jtreg.)
So the empirical question remains whether there are enough cases
that would benefit to warrant adding code. Efforts to find this
out would be welcome.


More information about the core-libs-dev mailing list