java.util.DualPivotQuickSort does not guarantee NlogN time

Jeff Hain jeffhain at
Mon Jan 26 21:15:43 UTC 2015


>It would be relatively easy to incorporate the basic idea of IntroSort (see

For the record, I tried (not too hard :) to get it piggy-backed into DualPivotQuickSort-related modifications,
but without success :

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.


More information about the core-libs-dev mailing list