java.util.DualPivotQuickSort does not guarantee NlogN time

[Jeff Hain]

Hi.

>It would be relatively easy to incorporate the basic idea of IntroSort (see http://en.wikipedia.org/wiki/Introsort)

For the record, I tried (not too hard :) to get it piggy-backed into DualPivotQuickSort-related modifications,
but without success :
http://mail.openjdk.java.net/pipermail/core-libs-dev/2010-September/004889.html

Note that those paranoid (like me) about quadratic hickups might also
be paranoid about memory and GC hickups due to Arrays.sort(...) creating
temporary arrays in some cases (big arrays especially hurt),
so they could still have to resort to a custom "QuietSort" class.

-Jeff