Timsort

Timsort

Timsort in action on a list of numbers. For short lists of numbers like this one, Timsort is equivalent to Insertion Sort
Class	Sorting algorithm
Data structure	Array
Worst-case performance	$\Theta (n\log n)$
Best-case performance	$\Theta (n)$
Average performance	$\Theta (n\log n)$
Worst-case space complexity	$\Theta (n)$
Optimal	Sometimes

Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002, for use in versions 2.3 and later of the Python programming language, and is also used in Java as well .

Tim Peters describes the algorithm as follows :

[...] an adaptive, stable, natural mergesort, modestly called

timsort (hey, I earned it <wink>). 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.

Like merge sort, it is a stable comparison sort with a worst-case time complexity of $\Theta (n\log n)$ .

According to information theory, no comparison sort can perform fewer than $\log _{2}(n!)$ comparisons in the average case, which requires that comparison sorting takes $\Omega (n\log n)$ time on random data. However, on real-world data, Timsort often requires far fewer than $\log _{2}(n!)$ comparisons, because it exploits the fact that sublists of the data may already be in order or reverse order.

See also

• Python (programming language)
• Mergesort
• Insertion sort

External links

• Visualising Timsort - the source for the image on this page.