Timsort: The Fastest sorting algorithm for real-world problems.
Awdesh Aug 14 Updated on Sep 14, 2018
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.
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.
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
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-:
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.
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.
- A > B + C
- B > C
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: (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.
- Images, gifs are taken from pexels and giphy respectively.
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.