Timsort

Timsort

A visual representation of timsort. For short lists such as this, 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	Yes

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 the Python programming language, and has been Python's standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7.

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 takes advantage of the fact that sublists of the data may already be in order or reverse order.

See also

• Mergesort
• Insertion sort
• Sorting algorithm

External links

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