Timsort

What is Timsort?

Originally invented by Tim Peters, for which it is named, in 2002 for use in the Python programming language, Timsort is considered to be a hybrid stable sorting algorithm. The reason it is considered to be a hybrid algorithm is because it combines certain facets of both merge sort and insertion sort. At a high level, the algorithm finds subsets of data that are already ordered and uses that to its advantage to sort the remaining portion of the data more efficiently.

Why know Timsort?

Besides being the defacto sorting algorithm of Python and the sorting mechanism of object arrays in Java 1.7 and newer, Timsort is one of the fastest sorting algorithms when used with real-world data. It combines the limited worst case run time performance of merge sort of O(n*log(n)) with the blazing best case performance of insertion sort of O(n).

Read More