Timsort

6 minute read

Timsort is a sorting algorithm that is efficient for real-world data and not created in a academic laboratory. Timsort was created by Tim Peters for the Python programming language in 2001. Timsort first analyses the list it is trying to sort and then chooses an approach based on the list.

Since the algorithm has been invented it has been used as the default sorting algorithm in Python, Java, the Android Platform, and in versions of GNU.

Timsort was designed to use already-ordered elements that already exist in most real-world data. It calls these already-ordered elements “natural runs”. It iterates over the data collecting the elements into runs, and simultaneously merging those runs together into one.

The array has fewer than 64 elements in it

[3, 2, 1, 9, 17, 34]

[1, 2, 3, 9, 17, 34]

[2, 3, 4, 17, 94]

[2, 3, 4, 17, 94]

If the array has fewer than 64 elements in it, timsort will execute an insertion sort.

An insertion sort is a simple sort which is most effective on small lists. It is quite slow at larger lists, but very fast with small lists. The idea of an insertion sort is as follows:

** Look at elements one by one ** Build up sorted list by inserting the element at the correct location

Here’s a trace table showing how insertion sort would sort the list [34, 10, 64, 51, 32, 21]

[34, 10, 64, 51, 32, 21] No. shifted to right
[34, 10, 64, 51, 32, 21] Nothing
[10, 34, 64, 51, 32, 21] 34
[10, 34, 64, 51, 32, 21] Nothing
[10, 34, 51, 64, 32, 21] 64
[10, 32, 34, 51, 64, 21] 34, 51, 64
[10, 21, 32, 34, 51, 64] 32, 34, 51, 64

In this instance we are inserting the newly sorted elements into a new sub-array, which starts at the start of the array.

Here’s a gif showing insertion sort:

img

More about runs

If the list is larger than 64 elements than the algorithm will make a first pass through the list looking for parts that are strictly increasing or decreasing. If the part is decreasing, it will reverse that part.

The minrun is a size which is determined based on the size of the array. It is selected so that most runs in a random array are, or become minrun, in length. Merging 2 arrays is more efficient when the number of runs is equal to, or slightly less than, a power of two. Timsort chooses minrun to try to ensure this efficiency.

Minrun is chosen from the range 32 to 64 inclusive, such that the length of the original array, when divided by minrun, is equal to or slightly less than a power of two.

If the run is less than minrun, you calculate the length of that run away from minrun. Using this new number, you grab that many items ahead of the run and perform an insertion sort to create a new run.

After this part has completed we should now have a bunch of sorted runs in a list.

Merging

Timsort now performs mergesort to merge the runs together, however, Timsort makes sure to maintain stabillity and merge balance whilest merge sorting.

In order to maintain stabillity we should not exchange 2 numbers of equal value. This not only keeps their original positions in the list but enables the algorithm to become faster.

As Timsort finds runs, it adds them to a stack. A simple stack would look like this:

a
b
c

Imagine a stack of plates. You cannot take plates from the bottom, so you have to take them from the top. The same is true about a stack.

Timsort tries to balance two competing needs when mergesort runs. On one hand, we would like to delay merging as long as possible in order to exploit patterns that may come up later. But we would like even more to do the merging as soon as possible to exploit the run that the run just found is still high in the memory hierachy. We also can’t delay merging “too long” because it consumes memory to remember the runs that are stil unmerged, and the stack has a fixed size.

To make sure we have this compromise, Timsort keeps track of the three most recent items on the stack and creates two laws that must hold true of those items:

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

In the words of Tim Peters himself:

What turned out to be a good compromise maintains two invariants on the stack entries, where A, B and C are the lengths of the three righmost not-yet merged slices

Usually, merging adjacent runs of different lengths in place - whilest maintaining stabillity is very hard. In order to get around this, Timsort sets aside temporary memory, and places the smaller (calling both runs A and B) of the two runs into that temporary memory.

Galloping

While Timsort is merging A and B, it notices that one run has been “winning” many times in a row. If it turned out that the run A consisted of entirely lower numbers than the run B, then the run A would just end up back in its origin place. Merging the two runs would involve a lot of work to achieve nothing.

More often than not, data will have some preexisting internal structure. Timsort takes advanage of this and assumes that if a lot of run A’s values are lower than run B’s values, then it is likely that A will continue to have smaller values than B.

Timsort will then enter galloping mode. Instead of checking A[0] (the first element of run A) and B[0] (the first element of run B) against each other, Timsort performs a binary search for the appropriate position of B[0] in A. This way, a whole section of A can be moved into place. Then it searches for the appropriate location of A[0] in B so a whole section of B can be moved at once.

Let’s see this in action. Timsort checks B[0] (which is 5) and using a binary search it looks for the correct location in A. Well, B[0] belongs at the back of the list of A. Now Timsort checks for A[0] (which is 1) in the correct location of B. So we’re looking to see where the number 1 goes. This number goes at the start of B. We now know that B belongs at the end of A and A belongs at the start of B.

In some implementations, we want to make sure that A can actually fit into B. We need to check A[-1] (the last element of A) to see if it is smaller than B[0]. Or if B is smaller, we need to check if B[-1] is smaller than A[0].

It turns out, this operation is not worth it if the appropriate location for B[0] is very close to the beginning of A (or vice versa), so gallop mode quickly exits if it isn’t paying off. Additionally, Timsort takes note, and makes it harder to enter gallop mode later by increasing the number of consecutive A-only or B-only wins required to enter. If gallop mode is paying off, Timsort makes it easier to reenter.

An interesting note: Though Timsort’s great performance on arrays with some preexisting internal sorting is its best-known feature, it seems like having a stable sort was one of the main motivators behind adopting timsort. Previously, in order to achieve a stable sort, you’d have to zip the items in your list up with integers, and sort it as an array of tuples. How irritating.

Coding it

I don’t know about you, but Timsort is confusing

https://bugs.python.org/file4451/timsort.txt

# Brandon Skerritt
# https://skerritt.tech
# you can do whatever you want with this 
# just make sure to follow me on social media 😜

def binary_search(the_array, item, start, end):
    if start == end:
        if the_array[start] > item:
            return start
        else:
            return start + 1
    if start > end:
        return start

    mid = round((start + end)/ 2)

    if the_array[mid] < item:
        return binary_search(the_array, item, mid + 1, end)

    elif the_array[mid] > item:
        return binary_search(the_array, item, start, mid - 1)

    else:
        return mid

"""
Insertion sort that the heap sort uses if the array size is small or if
the size of the "run" is small
"""
def insertion_sort(the_array):
    l = len(the_array)
    for index in range(1, l):
        value = the_array[index]
        pos = binary_search(the_array, value, 0, index - 1)
        the_array = the_array[:pos] + [value] + the_array[pos:index] + the_array[index+1:]
    return the_array

def merge(left, right):
    """Takes two sorted lists and returns a single sorted list by comparing the
    elements one at a time.
    [1, 2, 3, 4, 5, 6]
    """
    if not left:
        return right
    if not right:
        return left
    if left[0] < right[0]:
        return [left[0]] + merge(left[1:], right)
    return [right[0]] + merge(left, right[1:])

def timsort(the_array):
    runs, sorted_runs = [], []
    length = len(the_array)
    new_run = [the_array[0]]

    # for every i in the range of 1 to length of array
    for i in range(1, length):
        # if i is at the end of the list
        if i == length - 1:
            new_run.append(the_array[i])
            runs.append(new_run)
            break
        # if the i'th element of the array is less than the one before it
        if the_array[i] < the_array[i-1]:
            # if new_run is set to None (NULL)
            if not new_run:
                runs.append([the_array[i]])
                new_run.append(the_array[i])
            else:
                runs.append(new_run)
                new_run = []
        # else if its equal to or more than
        else:
            new_run.append(the_array[i])

    # for every item in runs, append it using insertion sort
    for item in runs:
        sorted_runs.append(insertion_sort(item))
    
    # for every run in sorted_runs, merge them
    sorted_array = []
    for run in sorted_runs:
        sorted_array = merge(sorted_array, run)

    print(sorted_array)

timsort([2, 3, 1, 5, 6, 7])

#webdev #compsci #webdeveloper #webdevelopment #thedevlife #coding #code #coder #webdesign #dev #devlife #geek #100daysofcode #blogging #javascript #programming #programmer #computerscience #developer #tech #computer #technology #frontend #js #buildtheweb #jquery #worldofprogrammers #softwareengineer #programmerrepublic

Categories:

Updated: