What is Timsort?

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,4(https://en.wikipedia.org/wiki/Timsort#cite_note-4) on the Android platform,5(https://en.wikipedia.org/wiki/Timsort#cite_note-5) in GNU Octave,6(https://en.wikipedia.org/wiki/Timsort#cite_note-6) on V8,7(https://en.wikipedia.org/wiki/Timsort#cite_note-7) Swift,8(https://en.wikipedia.org/wiki/Timsort#cite_note-8) and Rust.9(https://en.wikipedia.org/wiki/Timsort#cite_note-9)

It uses techniques from Peter McIlroy's 1993 paper "Optimistic Sorting and Information Theoretic Complexity".10(https://en.wikipedia.org/wiki/Timsort#cite_note-10)

TimSort is a sorting algorithm based on Insertion Sort and Merge Sort.

Used in Java’s Arrays.sort() as well as Python’s sorted() and sort(). First sort small pieces using Insertion Sort, then merges the pieces using a merge of merge sort. We divide the Array into blocks known as Run. We sort those runs using insertion sort one by one and then merge those runs using the combine function used in merge sort. If the size of the Array is less than run, then Array gets sorted just by using Insertion Sort. The size of the run may vary from 32 to 64 depending upon the size of the array. Note that the merge function performs well when size subarrays are powers of 2. The idea is based on the fact that insertion sort performs well for small arrays.

Details of the below implementation:

We consider the size of the run as 32 and the input array is divided into sub-array. We one-by-one sort pieces of size equal to run with a simple insertion sort. After sorting individual pieces, we merge them one by one with the merge sort. We double the size of merged subarrays after every iteration.

Timsort - Java Implementation

Timsort - Python Implementation

Complexity Analysis:

• Best Case | O(n)
• Average Case | O(n*log(n))
• Worst Case | O(n*log(n))
• Space | O(n)
• Stable | YES

Reference:

• https://en.wikipedia.org/wiki/Timsort
• https://www.geeksforgeeks.org/timsort/