No generic version of DualPivotQuickSort

[Buis, Paul]

Allowing the user to specify that they want an unstable sort or that they want a sort that takes minimal extra space at the price of being unstable, seems reasonable. I understand making the default behavior for sorting a generic type be doing a stable sort.

Arrays.sort(T[] a) should lead to a stable sort.

Adding either Arrays.sort(T[] a, boolean stable) or Arrays.unstableSort(T[] a) seems useful and forces the user to explicitly say they want an unstable sort for the marginal performance gain and/or the reduced memory requirement.

From: Louis Wasserman [mailto:lowasser at google.com]
Sent: Monday, January 26, 2015 4:02 PM
To: Buis, Paul; core-libs-dev at openjdk.java.net
Subject: Re: No generic version of DualPivotQuickSort

My understanding was that the performance difference wasn't perceived to outweigh the user confusion risks associated with multiple sorting algorithm options. Right now, only one option is presented -- a stable sort -- and that algorithm is intended to be *nearly* as fast as an unstable sort, and unstable sorting algorithms are *subtly* unsuitable for some use cases in a way that might be hard for users to debug or realize why their code is buggy.

Is that an accurate assessment?

On Mon Jan 26 2015 at 12:55:18 PM Buis, Paul <00pebuis at bsu.edu<mailto:00pebuis at bsu.edu>> 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)

or

static <T extends Comparable<? super T>> void sort(T[] a, int left, int right, T[] work, int workBase, int workLen)

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?