I've been investigating how to improve the performance of sorting an array that is already mostly sorted. Turns out java is replacing the
mergesort with
timsort in Java 7's
Arrays.sort. You can find the code
here. I'm seeing a factor of 3-4 improvement!