Discover order rather than ignore it
Timsort is an adaptive stable sorting approach that discovers naturally ordered runs and merges adjacent runs. A strictly descending run can be reversed to become ascending. Reversing a range containing equal keys can change their original relative order, so the descending-run rule needs care to retain stability. Short runs are extended, often through insertion sorting. The central idea is to exploit ordering already present in the input instead of treating every input as a completely unstructured collection or dividing it solely into fixed-size pieces without examining its contents.
Merge two runs by their frontiers
The sequence [1,4,7,2,3,8] contains ascending runs [1,4,7] and [2,3,8]. Comparing their frontiers produces 1,2,3,4,7,8. When equal keys occur on both sides, choosing the earlier left-side record first preserves their original order in a forward merge. Practical implementations can copy the shorter run into temporary storage and merge in either direction. The equal-key rule must be adjusted consistently for that direction. Tracking labeled records rather than only key values makes it possible to test stability and distinguish a correct merge from one that merely returns sorted numbers.
Merge scheduling affects total work
An input containing long runs can need fewer comparisons and moves than a similarly sized disordered input. If the whole array is one ascending run, recognizing it requires only a scan. However, repeatedly merging a huge run with a tiny neighbor in a poor schedule can move the same elements many times. Run-length-aware merge scheduling is therefore a separate important part of the design. The usual worst-case bounds are O(n log n) time and O(n) extra space, while adaptive analyses express additional benefits from the actual run structure. The method is not unconditionally linear.
Check the implementation’s merge policy
CPython’s official sorting design notes describe run detection and stable merging as well as changes to merge scheduling. Do not assume that an older presentation’s exact Timsort stack rules remain the policy in every current version: implementations may retain the run-based framework while using Powersort scheduling. Galloping, which takes larger blocks when comparisons repeatedly favor one run, is another implementation detail rather than a separate stability guarantee. Test repeated keys, reversed runs and many short runs. Comparator consistency and the availability of temporary storage are additional conditions that must be considered apart from the abstract merging strategy.