java.util.DualPivotQuickSort does not guarantee NlogN time

Jeff Hain jeffhain at
Tue Jan 27 23:52:16 UTC 2015

An ugly but non-intrusive workaround, that would not add much overhead for usual cases,taking advantage of quadraticness blowing up in stack overflow before long:

public class ParanoidSort {    public static void sort(Object[] a) {
        try {
        } catch (StackOverflowError e) {
            // Gone quadratic and array was too long.
            // Falling back to slower but safer sort,
            // hoping that array is not damaged.

Could also catch OOME there but I don't know if it's wise.


More information about the core-libs-dev mailing list