loading...
Cover image for Timsort:  The Fastest sorting algorithm for real-world problems.

Timsort: The Fastest sorting algorithm for real-world problems.

s_awdesh profile image Awdesh Updated on ・4 min read

Timsort was implemented by Tim Peters in 2002, it has been a standard sorting algorithm for Python since Python 2.3. Python's sorted and list. sort function uses Tim sort. Java uses Timsort in JDK for sorting nonprimitive types. Android platform and GNU Octave also uses it as a default sorting algorithm.

Timsort is a stable algorithm and beats every other sorting algorithm in time. It has O(nlogn) time complexity for worst case unlike quick sort and O(n) for best case scenarios unlike merge sort and heap sort.

In real-world scenarios, most of the times input array is naturally ordered array hence merge sort and quick sort aren't the efficient choices. Tim sort shines when data is ordered and of course when data is random.

Alt text of image

Why Tim sort is fast

Tim sort is a hybrid algorithm which uses Binary insertion sort and improved merge sort by using galloping (more on this later) in a combination. Binary insertion sort is the best method to sort when data is already or partially sorted and merge sort is best when the input is large.

Binary insertion sort uses Binary search to insert a new value in a sorted array. Binary search reduces the number of comparisons thus more efficient than linear search.

Sort

In above example, Binary insertion sort requires 2 iterations to find a location to insert 8 whereas a linear search would find a location in 4th iteration.

N: Number of elements inside the input array.

If N <= 64 then Tim sort uses binary insertion sort to sort the elements and doesn't go in fancy details.

What if N is large

An input array is divided into different sub-arrays, count of elements inside a sub-array is defined as a RUN, the minimum value of such runs is a MIN_RUN.

A RUN can be either ascending or strictly descending. If elements are decreasing then in place swapping converts them into ascending order, elements that have equal values aren't swapped to maintain stability
RUN

A run smaller than min run is extended to make count equal to min run. Now, this new run is sorted using binary insertion sort which has a best run time on partially ordered data. Ultimately, every run should be greater or equal to the min run and it shouldn't be less than 2.

Why Compute MIN_RUN

MIN_RUN ensures that the input array is split in such a way that when the merge happens, it happens in a perfectly balanced manner.

Let's understand it with an example below-:

Merge

In the left diagram above, we have 4 sub-arrays of size 2 which perform perfectly balanced merge at each step. In the right diagram, we have 5 sub-arrays of size 2 which doesn't allow the perfect balanced merge to happen.

Perfectly balanced merge allows one on one comparisons between items. An unbalanced merge can cause extra comparisons and impacts performance.

Ideally, Timsort wants the value of min run to be such that N / MIN_RUN equals to the power of 2 or close to it so that when the merge happens it gets a perfectly balanced merge for example When an input array has 256 elements Tim Sort would like to divide the array into equal sized sub-arrays. 256 / 32 will give us 8 equal sized sub-arrays that perform the perfectly balanced merge.

Merging

At this point, an input array has been divided into different sub-arrays and now they should be merged back to produce the final sorted array. Unlike merge sort, Tim sort uses a stack to store recent runs.

Timsort tries to delay merging as long as possible in order to exploit patterns that come up later but at the same time, it likes to merge as soon as possible because all the unmerged arrays are stored inside stacks and storing consumes memory which could hurt for a large array.

If we consider three sub-arrays A, B and C from left to right then Tim sort comply with below 2 variants to call merge_collapse() function to decide whether the current run should be merged with preceding runs or not.

  1. A > B + C
  2. B > C

stack

Merging two sub-arrays in place efficiently is very difficult and slow but if we have a temporary array this process can be faster and easier to implement. Tim sort uses temp array to perform the merge between two arrays.

Galloping

Gallop

Galloping: (of a process or time) progress rapidly in a seemingly uncontrollable manner.

Galloping is another technique used by Tim sort to further reduce comparisons while merging in order to increase the efficiency of an algorithm.

While merging two sub-arrays in a sorted manner Tim sort perform galloping. Galloping improves merging runtime by reducing comparisons. Java uses constant value '7' before it switches to Gallop mode. Galloping utilizes the binary search to make fewer comparisons during the merge procedure.

In below example, 101 is searched inside array A for 7 times and every time array B wins after 7th time Gallop mode is switched on which forces binary search for 101 inside A.

Now we compare 101 directly with A[mid] = 50 thus save lot of comparisons.
gallop

References

Conclusions

This was definitely one of the difficult posts to write because of the lack of resources to read about Tim sort. I am personally highly impressed by different optimization techniques used to achieve fast results in Tim sort.


If you want me to write on a specific topic, please feel free to post them in the comment section below.

You can support my work by buying me a coffee below. πŸ’šπŸ’šπŸ’šπŸ’šπŸ’šπŸ’š !!
Buy me a ko-fi

Posted on by:

s_awdesh profile

Awdesh

@s_awdesh

Learner, philomath. Engineer by choice humorous by nature.

Discussion

markdown guide
 

I wouldn't normally comment on these things, but I followed this link (hackernoon.com/timsort-the-fastest...) posted by Michael Kohl in the comments and... I'll be blunt and say this is just a slightly modified copy of that article (even the section headings are the same!). If you want a better and more honest read, follow the link and skip this article.

Awdesh, please don't just copy random articles on the web and post them as your own.

 

Wow. Thanks for your feedback Rui Rei.

I don't know which part of the article you think is copied. A considerable amount of time being spent on understanding this algorithm from original python and Java docs (referenced) hence different hand drawn diagram.

Original article that is referenced uses similar section headings to keep concepts segregated.

 
 

TQ, a great post. Need to revisit a few times to get a hang of it.

 

Thank you. Yeah, there's a lot of information to digest in this algorithm.

 
 

In above example, Binary insertion sort requires 2 iterations to find a location to insert 8.

I think it should requires 3 iterations.

  1. 0-7, mid=3
  2. 0-3, mid=1
  3. 1-3, mid=2