4 ms·
Yes, 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" siz
by beagle3 13y ago
Yes, 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...