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
