Timsort implementation in Python

Question

I wanted to implement a Timsort in python.

Here's what I've come up with:

from typing import List

RUN = 32

def insertionSort(unsorted: List[int], left: int, right: int) -> None:
    """ Sorts the array using insertion sort """

    for i in range(left + 1, right + 1):
        temp = unsorted[i]
        j = i-1

        while unsorted[j] > temp and j >= left:
            unsorted[j+1] = unsorted[j]
            j -= 1

        unsorted[j+1] = temp

def merge(unsorted: List[int], left: int, middle: int, right: int) -> None:
    """ Merges two sorted arrays """

    len1 = middle - left + 1
    len2 = right - middle

    left_side  = unsorted[left : left + len1]
    right_side = unsorted[middle + 1 : middle + len2 + 1]

    i = j = 0
    k = left

    while i < len1 and j < len2:
        if left_side[i] <= right_side[j]:
            unsorted[k] = left_side[i]
            i += 1
        else:
            unsorted[k] = right_side[j]
            j += 1

        k += 1

    while i < len1:
        unsorted[k] = left_side[i]
        i += 1
        k += 1

    while j < len2:
        unsorted[k] = right_side[j]
        j += 1
        k += 1

def timSort(unsorted: List[int], length: int) -> None:
    """

    Sorts every 'RUN' elements by insertion sort as
            insertion sort is faster for smaller array lengths

    """

    # Sorts every RUN elements using insertion sort
    for i in range(0, length, RUN):
        insertionSort(unsorted, i, min(i + 31, length - 1))

    size = RUN

    # Merges every sorted subarray using Merge Sort
    while size < length:
        left = 0

        while left < length:
            mid = min(left + size - 1, length - 1)
            right = min(left + 2 * size - 1, length - 1)

            merge(unsorted, left, mid, right)

            left += size * 2

        size *= 2

if __name__ == '__main__':
    unsorted = list(map(int, input('Enter space seperated elements: ').split()))
    n = len(unsorted)

    timSort(unsorted, n)

    print('Here\'s the sorted array: ')
    print(*unsorted)

I think it looks good, but I want to make it even better.

PS: What would be the optimal length for RUN?

Answer 1

The easiest way to implement Timsort in Python is of course to use the built-in version:

def timsort(x):
    return sorted(x)

Since you don't learn anything from that, implementing it yourself is of course nice.

First, some general comments.

• Python has an official style-guide, PEP8. It recommends using lower_case for variables and functions. It also recommends using empty lines sparingly.
• You don't need to pass the length to the algorithm. Every indexable Python object has a length, so just use len(unsorted).
• Your type hints say that this function can only take lists of integers. It works perfectly fine with lists of any comparable type, just like the built-in sorted.
• Choosing to modify the input list in-place is perfectly fine for lists (after all, list.sort does the same thing). But if you do that, it should be noted in the docstring. You could, however, also choose to conform closer to sorted and first copy the iterable into a list (simply copying if it already is a list), sorting it in-place and returning it. This would change the signature to tim_sort(x: Iterable[Any]) -> List[Any].
• The built-in sorting functions all take a key argument, which is called once per argument. This results in effectively sorting [key(element) for element in x] and afterwards returning only the second element from each inner tuple.

Now, let's take a closer look at your actual code.

You use while loops quite a lot. While (pun intended) they almost always work, they are not always the most efficient (in readability) way to accomplish your goal. In the merge function you can replace the last two while loops with list slice assignments. I would also simplify the setting of left_side and right_side by using left, middle and right instead of left, middle, len1 and len2.

def merge(unsorted: List[int], left: int, middle: int, right: int) -> None:
    """ Merges two sorted arrays """
    len1 = middle - left + 1
    len2 = right - middle
    left_side  = unsorted[left:middle + 1]
    right_side = unsorted[middle + 1:right + 1]
    
    i = j = 0
    k = left
    while i < len1 and j < len2:
        if left_side[i] <= right_side[j]:
            unsorted[k] = left_side[i]
            i += 1
        else:
            unsorted[k] = right_side[j]
            j += 1
        k += 1

    unsorted[k:] = left_side[i:]
    unsorted[k + len1 - i:] = right_side[j:]

Instead of slices, you can also create a new list and use extend:

def merge(unsorted: List[int], left: int, middle: int, right: int) -> None:
    """ Merges two sorted arrays """
    len1 = middle - left + 1
    len2 = right - middle
    left_side  = unsorted[left:middle + 1]
    right_side = unsorted[middle + 1:right + 1]
    
    i = j = 0
    k = left
    out = []
    while i < len1 and j < len2:
        if left_side[i] <= right_side[j]:
            out.append(left_side[i])
            i += 1
        else:
            out.append(right_side[j])
            j += 1
        k += 1
    out.extend(left_side[i:])
    out.extend(right_side[j:])
    unsorted[:] = out

The first while loop could also use iterators instead of indices, but that is left as an exercise for now.