Skip to content

Big O Visualizer

Tim Sort

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsequences of the data that are already ordered (runs) and uses them to sort the remainder more efficiently. This is done by merging runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, on V8, and Swift.

Complexity

Tim Sort has a linear best-case time complexity, which can be tested using a list of identical numbers.

Tim Sort performs significantly better than linearithmic for a variety of sorted lists of numbers.

Tim Sort performs about linearithmic for a variety of lists of numbers. What these lists have in common is that they contain partially ordered numbers inside them.

In the next test, three blended lists are sorted. A blended list is build by combining more than ten different data sets in order to produce a list that is part random, part sorted, part reversed, part zigzag, part zeroes and so on.

Finally, Tim Sort has a linearithmic worst-case time complexity, which can be tested using a random list of numbers.

Algorithm

Click here to see the implementation used on this page and click here to see the original algorithm it's based on.