Timsort

Timsort is a hybrid sorting algorithm, which is derived from the insertion site, and merge sort. It was designed to work quickly on the various real data. It was developed in 2002 by Tim Peters for use in Python and is in Python since version 2.3 of the standard sorting algorithm. Meanwhile, it is used for sorting arrays and on the Android Platform in Java SE 7.

Tim Peters describes the algorithm as follows:

" [ ... ] To adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it ). It has supernatural performance on many kinds of Partially ordered arrays (less than lg ( N! ) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned Samplesort hybrid on random arrays.

In a nutshell, the main routine marches over the array once, left to right, Alternately Identifying the next run, then merging it into the previous runs " intelligently ". Everything else is complication for speed, and some hard -won measure of memory efficiency. "

There is already sorted parts in the data. Descending sorted parts are reversed. Then it is checked whether the length of the sections reaches the minimum cut-off length for the particular array size. The minimum segment length depends on the size of the array. For arrays with less than 64 elements of the minimum section length is the entire array, so that in the case corresponding to a timsort insertion site. For larger arrays, a number between 32 and 64 is selected as the minimum section length, so that the size of the array divided by the minimum section length is equal to or slightly smaller than the a power of two. The algorithm simply uses the six most significant bits of the array length and adds one to, if not at least one of the other bits is set. When a portion does not reach the minimum segment length, it is increased with the insertion site until it is long enough. The sections are then joined together by mergesort to finish the sorted array.

How mergesort is a stable timsort, comparison -based sorting algorithm with a best-case complexity and worst- and average-case complexity of.

According to the information theory can get along no comparison -based sorting algorithm with less than Ω (n log n ) comparisons in the average-case. On real data timsort needs often significantly less than Ω (n log n ) comparisons, because it benefits from the fact that parts of the data are already sorted.