Replaced primitive sorts with Iaroslavski, Bentley, and Bloch's Dual Pivot Quicksort.
The originals were based on Bentley and McIlroy's "Engineering a Sort Function."
The original floating point sorts suffered from poor performance due to the use
of a naive comparison function. In round numbers, the new version is 1.5x as fast
as the old one on integers and twice as fast on floating point numbers (on the
latest Android build running on Sholes). On some data sets (e.g., nearly sorted data,
the new version is substantially faster.
Now, with added performance tweaks from Jesse and Bob!! With these tweaks, the sort
is 70% faster than the original sort on integers and over twice as fast on doubles.
None of the optimizations are Dalvik-specific, and we may be able to make it even
faster by adding Dalvik-specific optimizations.
Also added beefier tests.
3 files changed