Timsort

Timsort is the default sorting implementation in Python. It is a hybrid sort that uses binary insertion sort and merge sort. It is also adaptive. This means that the algorithm will behave differently based on the input factors. In a sense, the algorithm tries to select the optimal sorting approach to a particular input based on different properties of that input such as input size. The main idea behind timsort is to leverage natural runs. Natural runs are subsets of the initial input data that are ordered. In other words, the input data may have subsections that are already sorted. For a completely random distribution this approach does not offer any improvement, but most data sets are will have ordered subsets. Tim sort has minrun variable that defines the smallest size of an ordered subset such that it is treated as a natural run. Runs that have are below this threshold are build up using binary insertion. Once runs are identified the merge subroutine combines consecutive runs. (note a run could be as small as two elements)

In summary, timsort uses the idea of natural runs to increase performance when operating on sets that have ordered subsets. Runs are build up from ordered subsets and then combined using the merge subroutine. So essentially search space is split up into smaller chunks which are then sorted using insertion sort and everything is put back together using merge sort. Something to note here, is that timsort is not optimized for totally random distributions, and the adaptive overhead of the algorithm will probably slow it down when dealing with random data.