Algorithms
Raiting:
7

Sorting algorithm Timsort


Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python, OpenJDK 7 and Android JDK 1.5. Here is a table in order to understand that better from Wikipedia.

image

There are only 7 of adequate algorithms among a huge selection in the table (with complexity O(n logn)), but only two of them have stability and complexity of O(n) at best. One of the two is long well known to everyone "Tree sort that builds a binary search tree", and the second one is Timsort.

Timsort is designed to take advantage of partial ordering that already exists in most real-world data. Timsort operates by finding runs in the data. A run is a sub-array, at least two elements long, which is either non-descending or strictly descending. If it is descending, it must be strictly descending, since these runs are later reversed by a simple swap of elements from both ends converging in the middle. This method is stable if the elements are present in a strictly descending order. After obtaining such a run in the given array, Timsort processes it; and then continues its search for the next run.

Let’s get straight to the point


Do not expect here some complex mathematical discoveries. The fact is that Timsort is not entirely independent algorithm, but it is a hybrid, an effective combination of several other algorithms. Briefly, the essence of the algorithm can be explained as follows:

1. Divide an input array into sub-arrays by a special algorithm.
2. Sort each sub-array by insertion sort.
3. Gather the sorted sub-arrays into a single array using a modified merge sort.

The keys are always hiding in details, namely they are the algorithm and a modified merge sort.

Algorithm


Here are the used concepts

• N - the size of the input array
• run - sorted sub-array in the input array. Moreover, sorted non-ascending or strictly descending order. That is «a0 <= a1 <= a2 <= ...», or« a0> a1> a2> ... »
• minrun - as mentioned above, the input array is divided into sub-arrays. minrun - the minimum size of the sub-array. This number is calculated by certain logic of the number N.

image

Step 0. minrun calculation.

Number minrun is determined on the basis of N in terms of the following principles:

1. It should not be too large as far as insertion sort will be further applied to the sub-array of the size of minrun, but it is effective only for small arrays.
2. It should not be too small, because the smaller is sub-array the more merging iterations of sub-arrays should be done at the last step of the algorithm.
3. It would be nice if the optimal value for N / minrun is a power of number 2 (or close to it). This requirement determined by the merging algorithm of sub-arrays that works most efficiently in sub-arrays of equal size.

At this point the algorithm's author refers to the own experiments that showed when minrun >256 clause 1 is broken, minrun <8 clause 2 is broken and the most effective to use values from a range (32 to 65). Exception - if N <64, then minrun = N and Timsort converts into a simple insertion sort. The final algorithm for this simply takes the most significant six bits of the size of the array, adds one if any of the remaining bits are set, and uses that as the minrun. A sample code looks like this:

int GetMinrun(int n)
{
int r = 0; /* станет 1 если среди сдвинутых битов будет хотя бы 1 ненулевой */
while (n >= 64) {
r |= n & 1;
n >>= 1;
}
return n + r;
}

Step 1. Dividing into sub-arrays and sorting them out.

So, at this stage we have the input array, its size is N and the calculated number of minrun. Here are the steps:

1. Set the pointer of the current element to the top of the input array.
2. Look for the input arrayrun (sorted sub-array) beginning with the current element. By definition, this run will definitely include the current element and the following one. If the resulting sub-array is sorted in descending order - swap the elements so they go in ascending order (this is a simple linear algorithm).
3. If the size of the current run is less than minrun - take next elements in the minrun - size (run). Thus, we get a sub-array of the size of the minrun or greater in the output, the part of which (ideally, it should be all) is sorted.
4. Use insertion sort to the sub-array, since the size of the sub-array is small and some of it is already sorted, the sorting works quickly and efficiently.
5. Set the pointer of the current element on the following element after the sub-array.
6. If the end of input array is not gotten - go to the step 2.

Step 2. Merge.

At this stage we have an input array broken into sub-arrays, each of them is sorted. If the input array data was close to random - the size of the sorted sub-arrays is close to minrun. If the ranges were sorted in data – the sorted sub-arrays have a size exceeding minrun.
Now we need to merge these sub-arrays in the final ordered array meeting 2 requirements:

1. Merge sub-arrays in the equal size (so it turns out better).
2. Keep the stability of the algorithm, namely there is no need to do any pointless swaps.

This is achieved in this way.

1. Create an empty stack of pairs <sub-array starting index> - <sub-array size>. Take the first sorted sub-array.
2. Add some data in the stack < start index > - <size> for the current sub-array.
3. For this, the three top-most runs in the stack which are unsorted are considered. If, say, X, Y, Z represent the lengths of the three uppermost runs in the stack, the algorithm merges the runs so that ultimately the following two rules are satisfied:
X> Y + Z
Y> Z
4. If the first of the two rules is not satisfied by the current run status, that is, if X < Y + Z, then, Y is merged with the smaller of X and Z. The merging continues until both the rules are satisfied.
5. Then the algorithm goes on to determine the next run.

The rules above aim at maintaining run lengths as close to each other as possible to ensure balanced merges, which are more efficient.

image

Let us imagine an ideal situation: we have the sub-arrays of the size of 128, 64, 32, 16, 8, 4, 2, 2 (forget for a moment about the requirements of "the size of the sub-array> = minrun»). In this case, any mergers would not be executed until it reaches the last 2 sub-arrays, but after that there will be executed 7 perfectly balanced merges.

Merging procedure for the sub-arrays


As we remember in the second step of the algorithm, we merge the two sub-arrays into one sorted. We always merge two consecutive sub-arrays. An additional memory is used for their merger.

1. Create a temporary array in the size of the smaller from merging sub-arrays.
2. Copy a smaller one into a temporary array.
3. Set the pointers of the current position on the first elements of a larger and a temporary array.
4. At each step we consider the value of the current elements in the larger and temporary arrays, and then take smaller of them and copy it into a new sorted array, then move the pointer of the current element in the array from which was taken the element.
5. Repeat #4 until one of the arrays will not end.
6. Add all the remaining elements of the array to the end of the new array.

image

Modification of merging procedure for the sub-arrays


Everything seems to be well in the above merging algorithm. Except one, let us imagine a merger of two such arrays here:
A = {1, 2, 3 ,..., 9999, 10000}
B = {20000, 20001, ...., 29 999, 30000}
The above mentioned procedure would definitely work for them, but each time in its 4thclause will be needed to do one matching and one copy. In total there will be 10000 matching and 10000 copies. Timsort algorithm offers modification at this point, which is called the "gallop." Here are the main points if this modification:

1. Start a merging procedure, as it was shown above.
2. Remember from what sub-array was the element at each operation of element copy from a temporary or larger sub-array into the resulting.
3. If a number of elements (in this algorithm implementation the number is strictly equal to 7) was taken from the same array, it is assumed that we will continue to take data from it. To confirm this idea, we go to the galloping mode, namely in this mode we use the previously mentioned adaptation of binary search to identify where the first element of the smaller array must be placed in the larger array and vice-verse. Thus the entire set of elements, in one array, occurring before this location can be moved all together to the merge area and the other way round.
4. When the data is no longer fit from the current array (or when we come to the end of array), we can finally copy them all at once (which may be more effective than single element copying).

Perhaps, the explanation is slightly hazy, let us try an example:
A = {1, 2, 3 ,..., 9999, 10000}
B = {20000, 20001, ...., 29 999, 30000}

1. The first 7 iterations 1, 2, 3, 4, 5, 6 and 7 from the array A are being compared with the number 20000, and after we made certain that 20000 is greater - copy the elements of the array A in the resulting one.
2. When in galloping mode: this is done by comparing that with the number 20000, then 8, 10, 14, 22, 38, n+2^i, …, 10000 of the array A.
3. We reached the end of the array A, and we know that it is less than B (we might stop as well somewhere in the middle). Copy the needed data from the array A in the resulting one, and so on.

That is the whole algorithm.

Related references:


Timsort from Wikipedia
Presentation of the algorithm from a creator
Algorithm discussion on Stackoverflow
Beautiful visualization of the algorithm
Pirat 14 january 2012, 11:40
Vote for this post
Bring it to the Main Page
 

Comments

Leave a Reply

B
I
U
S
Help
Avaible tags
  • <b>...</b>highlighting important text on the page in bold
  • <i>..</i>highlighting important text on the page in italic
  • <u>...</u>allocated with tag <u> text shownas underlined
  • <s>...</s>allocated with tag <s> text shown as strikethrough
  • <sup>...</sup>, <sub>...</sub>text in the tag <sup> appears as a superscript, <sub> - subscript
  • <blockquote>...</blockquote>For  highlight citation, use the tag <blockquote>
  • <code lang="lang">...</code>highlighting the program code (supported by bash, cpp, cs, css, xml, html, java, javascript, lisp, lua, php, perl, python, ruby, sql, scala, text)
  • <a href="http://...">...</a>link, specify the desired Internet address in the href attribute
  • <img src="http://..." alt="text" />specify the full path of image in the src attribute