Some time ago I wrote on inefficient sorting in
java.util.Arrays. In upcoming JDK 7 things seem to get better.
Joshua Bloch has changed the implementation of
Arrays.sort(Object) method to use TimSort instead of Mergesort. This algorithm requires array allocation of size small constant to
n/2 and fewer than
n log(n) comparisons, just
n for almost sorted arrays. Unfortunately
Collections.sort(Object) still dump a collection into an array.
Another improvement was made by Vladimir Yaroslavskiy et al. who replaced implementation of Quicksort in
Arrays.sort(array of primitives) with Dual-Pivot Quicksort he invented. It offers roughly the same number of comparisons as Quicksort, but 20% fewer swaps. Tests show up to 50% or even 100% performance boost on some datasets.
Let see the numbers for JDK 7 performance.