Some time ago I wrote on inefficient sorting in java.util.Collections and 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.