# Is Timsort more efficient than merge sort and why?

I was just wondering, I think merge sort is more efficient but not sure if that is true. I know it's to do with the complexities but am still struggling to understand.

• Timsort is just an implementation-details of natural mergesort. Part of the challenge of implementing natural mergesort is to determine when to merge runs and which runs. Timsort has its own way of detecting runs and merging them, and resort to insertion sort when runs are small enough, while keeping them stable. – garbagecollector Aug 25 at 19:57

In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements.
Timsort uses insertion sort for very small amounts of data; this is typically more efficient than a pure merge sort because the benefits of merge sort over insertion sort are asymptotic. Merge sort is asymptotically faster than insertion sorts, which means that there is a threshold $N$ such that if $n \ge N$ then sorting $n$ elements with merge sort is faster than with insertion sort. The numerical value of threshold depends on the specific implementations though. With typical optimized implementations, insertion sort beats merge sort for a small amount of data. Most sort routines in the real world are hybrid, using an $O(n \log n)$, divide-and-conquer technique for large amounts of data and using a different technique (usually insertion sort) when they've broken down the data into small enough pieces. Thus a properly implemented timsort is faster on average than a pure merge sort.