Merge-Sort is popularly considered one of the most (time-)efficient sorting algorithms. It’s natural to assume that all standard sorting libraries in different programming languages would use it or variations of it.

Today I learned that the list.sort(...) method in Python uses Tim-Sort¹ which uses techniques from merge (divide and conquer & merge operations) and insertion sort (sorting sub-arrays).

The time complexity is still O(NlogN) and the space complexity is O(N), where N is the size of input.

What’s interesting is that Tim-Sort only uses extra space (affected linearly) if required.