Timsort Implementation Using C++

The Timsort is a stable sorting algorithm that uses the idea of merge sort and insertion sort. It can also be called a hybrid algorithm of insertion and merge sort.  It is widely used in Java, Python, C, and C++ inbuilt sort algorithms. The idea behind this algorithm is to sort small chunks using insertion sort and then merge all the big chunks using the merge function of the merge sort algorithm.

Working

In this algorithm, the array is divided into small chunks. The chunks are known as RUN. Each RUN is taken and sorted using the insertion sort technique. After all the RUN are sorted, these are merged using the merge function. There may be a case where the size of the array can be less than RUN. In such a case, the array is sorted by the insertion sort technique. Usually, the RUN chunk varies from 32 to 64, depending on the size of the array. The merge function will only merge if the subarray chunk has the size of powers of 2.

The advantage of using insertion sort is because insertion sort works fine for the array with a small size.

Time complexity –

Best case – Omega(n)

Average case – O(nlogn)

Worst case – O(nlogn)

C++ code –

Pin It on Pinterest

Share This