3 ms·
Previous innovation that I remember in sorting was Python's TimSort - it's just MergeSort with a few tweaks, but it's better than any other sort I've met when a
by beagle3 13y ago
Previous innovation that I remember in sorting was Python's TimSort - it's just MergeSort with a few tweaks, but it's better than any other sort I've met when applied to real world data.
- masklinn 13y ago> it's just MergeSort with a few tweaks "a few tweaks" is a bit of an understatement, at a high-level it's a hybrid of insertion and merge sort (it's an insertion sort below 64 elements, and it uses insertion sorts to create sorted sub-sections of 32~64 elements before applying the main merge sort)
- beagle3 13y agoYes, it is a bit of understatement. Other than the insertion at smaller sizes, it adds: - scans array to find merge-able runs (rather than use a "standard" size like more merge sorts); This makes it closer to O(n) for mostly-sorted arrays, a feature that is mostly associated with Bubble Sorts - but without giving up any of the good things about MergeSort - identifies "reverse runs", and just reverses them - making mostly-reverse-sorted arrays closer to O(n), which no other general sort achieves. It's still O(n log n) in the worst case - but it just works exceptionally well on real life datasets, which often have sorted or reversed sections.
- TwoBit 13y agoOur benchmarks consistently show Tim sort as the fastest -stable- sort, But intro sort consistently beats it.
- beagle3 13y agoWhich benchmarks would that be? TimSort as implemented in Python goes through the Python machinery of object comparison and object management in general. Make sure you do an apples<->apples comparison when benchmarking.
- stuhood 13y agoTimsort is in JDK7, btw. http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/TimSort.java http://grepcode.com/file/repository.grepcode.com/java/root/j...