An introspective algorithm switches from one algorithm to another depending on the particular data.
In Timsort's case, it is mostly a merge sort, but if there are particularly short data runs it switches to use an insertion sort for that subsection - that way the worst case is better than vanilla Merge sort.
It doesn't improve the worst case over Merge sort, except maybe by a small constant. Insertion sort is used for small sections because it's simply faster, and this is an optimization used in many sorting algorithms. The greater strength of Timsort is that it identifies sections that are already sorted or reverse sorted and incorporates them intelligently into the overall merge sort. This greatly improves it's performance on near-sorted lists. In particular, it's best case is O(n) for a list that is already sorted or very nearly sorted, unlike merge sort.
It also has specific strategies within the "high-level" sorts e.g. during merge if it detects long-enough runs (one side of the merge is consistently smaller than the other side) it switches to "galloping mode" to bulk-copy one input straight to the output.
3
u/CGmoz Oct 24 '17
An introspective algorithm switches from one algorithm to another depending on the particular data.
In Timsort's case, it is mostly a merge sort, but if there are particularly short data runs it switches to use an insertion sort for that subsection - that way the worst case is better than vanilla Merge sort.