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, OpenJDK 7 and Android JDK 1.5. Here is a table in order to understand that better from Wikipedia.


There are only 7 of adequate algorithms among a huge selection in the table (with complexity O(n logn)), but only two of them have stability and complexity of O(n) at best. One of the two is long well known to everyone "Tree sort that builds a binary search tree", and the second one is Timsort.
Pirat 14 january 2012, 11:40