Actually, another case: Vladimir Yaroslavskiy recently came up with a dual-pivot quicksort method where the number of swaps is reduced from 1nln(n) to 0.8nln(n)

Actually, another case: Vladimir Yaroslavskiy recently came up with a dual-pivot quicksort method where the number of swaps is reduced from 1nln(n) to 0.8nln(n). Yes, he's only twiddling the constant factor, but the benchmarks have been promising, with some sorts being reduced to 25% to 50% of their previous running time. Josh Bloch, one of the shepherds of Java, took the time to implement it as the default sorting algorithm in Java 7 (whenever that gets released). More details at: http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs... How timsort from Python stacks up, I don't know offhand. But that's a different beast instead of an improvement to a fundamental algorithm.