21 October 2010

Efficiently sorting an array that is already mostly sorted

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!

17 October 2010