No generic version of DualPivotQuickSort

[Doug Lea]

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.

-Doug