# Timsort implementation in Python

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?

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.

• 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.

• That's not the easiest way, easiest way is timsort = sorted :-P (then you even get its parameters for free) – superb rain Oct 5 at 9:52
• @superbrain: I would argue that "The easiest way to implement Timsort in Python is of course to use the built-in version" is still true, but I did not give the simplest possible implementation of that :D And you are right, getting the options for free without having to do *args, **kwargs is nice. – Graipher Oct 5 at 9:55
• [(key(element), element) for element in x] isn't quite right, since the element itself is not used in the comparisons then, only the key is. More seriously: Your merge functions don't work, cause TypeError: 'list_iterator' object is not subscriptable. – superb rain Oct 5 at 10:10
• Plus your first merge would remove everything right of right and your second merge would also remove everything left of left. The slice assignments need to take those bounds into account. – superb rain Oct 5 at 10:15
• @superbrain: Looks like somebody didn't test their code...I'll see if I can fix it up. – Graipher Oct 5 at 10:17