"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)
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.
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.
"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)