Updated April 1, 2023
Introduction to Timsort Python
The hybrid of the two sorting algorithms, insertion sort algorithm and merge sort algorithm, is called the Timsort algorithm in Python. Timsort algorithm can be used on real-time data to sort the data. This Timsort algorithm is a very stable algorithm which divides the given array to be sorted into blocks, each known as the run whose length must be either 32 or 64 posts which the elements of the individual blocks are sorted using insertion sort algorithm and then the sorted blocks are merged together using merge sort algorithm, and in each iteration, the size of the merged array is doubled.
Function to perform Timsort in Python:
Code:
def timsort(inputarray):
arraysize = len(inputarray)
minlengthrun = find_minlengthrun(arraysize)
for start in range(0, arraysize, minlengthrun):
end = min(start + minlengthrun - 1, arraysize - 1)
insertionsort(inputarray, start, end)
mergedarraysize = minlengthrun
while mergedarraysize < arraysize:
for left in range(0, arraysize, 2 * mergedarraysize):
mid = min(arraysize - 1, left + mergedarraysize - 1)
right = min((left + 2 * mergedarraysize - 1), (arraysize - 1))
merge(inputarray, left, mid, right)
mergedarraysize = 2 * mergedarraysize
Where inputarray is the input array to be sorted using the Timsort algorithm, arraysize is the length of the inputarray, minlengthrun is the minimum length of each run.
Working of Timsort Algorithm in Python
- The first step in the Timsort algorithm is to divide the given array into blocks which are also called runs.
- The next step is to find the minimum length of each run.
- Then the next step is to split the elements of each and sort them using the insertion sort algorithm.
- The final step is to merge each of the sorted run together using a merge sort algorithm to form a sorted array.
- We have to make sure that the length of each run is not too short as smaller length runs require many number of iterations in the merge sort technique to merge the runs.
Examples of Timsort Python
Given below are the examples of Timsort Python:
Example #1
Python program to sort the elements of the given array by implementing Timsort algorithm and then display the sorted elements of the array.
Code:
#defining the minimum value which indicates the limit for the length of each run
minimum= 32
#defining the function to find out the minimum length in each run
def find_minlengthrun(arraysize):
a = 0
while arraysize >= minimum:
a |= arraysize & 1
arraysize >>= 1
return arraysize + a
#defining insertionsort function to sort the elements of each run
def insertionsort(inputarray, left, right):
for b in range(left+1,right+1):
eachelement = array[b]
c = b-1
while eachelement<inputarray[c] and c>=left :
inputarray[c+1] = inputarray[c]
c -= 1
inputarray[c+1] = eachelement
return inputarray
#defining mergesort function to merge each sorted run into a single sorted array
def merge(inputarray, d, e, a):
arraylength1= e - d + 1
arraylength2 = q - e
left = []
right = []
for f in range(0, arraylength1):
left.append(inputarray[d + f])
for f in range(0, arraylength2):
right.append(inputarray[e + 1 + f])
f=0
g=0
h=d
while g < arraylength2 and f < arraylength1:
if left[f] <= right[g]:
inputarray[h] = left[f]
f += 1
else:
inputarray[f] = right[g]
g += 1
h += 1
while f < arraylength1:
inputarray[h] = left[f]
g += 1
f += 1
while g < arraylength2:
inputarray[h] = right[g]
h += 1
g += 1
#defining timsort function to sort the elements of the given array using insertion sort and merge sort function
def timsort(inputarray):
arraysize = len(inputarray)
minlengthrun = find_minlengthrun(arraysize)
for start in range(0, arraysize, minlengthrun):
end = min(start + minlengthrun - 1, arraysize - 1)
insertionsort(inputarray, start, end)
mergedarraysize = minlengthrun
while mergedarraysize < arraysize:
for left in range(0, arraysize, 2 * mergedarraysize):
mid = min(arraysize - 1, left + mergedarraysize - 1)
right = min((left + 2 * mergedarraysize - 1), (arraysize - 1))
merge(inputarray, left, mid, right)
mergedarraysize = 2 * mergedarraysize
#defining the array to be sorted
array = [100, 40, 60, 20, 30, 70, 50, 80, 90, 10]
print("The elements of the array before sorting are:")
print(array)
timsort(array)
print("The elements of the array after sorting are:")
print(array)Output:
In the above program, we are defining a function to find the minimum length of each run. Then we are defining the insertion sort function to sort the elements of each run. Then we are defining the merge sort function to merge each sorted run to a single sorted array. Then we are defining the timsort function, which divides each array into blocks called run and uses the insertion sort and merge sort function to sort the elements of the given array.
Example #2
Python program to sort the elements of the given array by implementing Timsort algorithm and then display the sorted elements of the array.
Code:
#defining the minimum value which indicates the limit for the length of each run
minimum= 32
#defining the function to find out the minimum length in each run
def find_minlengthrun(arraysize):
a = 0
while arraysize >= minimum:
a |= arraysize & 1
arraysize >>= 1
return arraysize + a
#defining insertionsort function to sort the elements of each run
def insertionsort(inputarray, left, right):
for b in range(left+1,right+1):
eachelement = array[b]
c = b-1
while eachelement<inputarray[c] and c>=left :
inputarray[c+1] = inputarray[c]
c -= 1
inputarray[c+1] = eachelement
return inputarray
#defining mergesort function to merge each sorted run into a single sorted array
def merge(inputarray, d, e, a):
arraylength1= e - d + 1
arraylength2 = q - e
left = []
right = []
for f in range(0, arraylength1):
left.append(inputarray[d + f])
for f in range(0, arraylength2):
right.append(inputarray[e + 1 + f])
f=0
g=0
h=d
while g < arraylength2 and f < arraylength1:
if left[f] <= right[g]:
inputarray[h] = left[f]
f += 1
else:
inputarray[f] = right[g]
g += 1
h += 1
while f < arraylength1:
inputarray[h] = left[f]
g += 1
f += 1
while g < arraylength2:
inputarray[h] = right[g]
h += 1
g += 1
#defining timsort function to sort the elements of the given array using insertion sort and merge sort function
def timsort(inputarray):
arraysize = len(inputarray)
minlengthrun = find_minlengthrun(arraysize)
for start in range(0, arraysize, minlengthrun):
end = min(start + minlengthrun - 1, arraysize - 1)
insertionsort(inputarray, start, end)
mergedarraysize = minlengthrun
while mergedarraysize < arraysize:
for left in range(0, arraysize, 2 * mergedarraysize):
mid = min(arraysize - 1, left + mergedarraysize - 1)
right = min((left + 2 * mergedarraysize - 1), (arraysize - 1))
merge(inputarray, left, mid, right)
mergedarraysize = 2 * mergedarraysize
#defining the array to be sorted
array = [10, 4, 6, 2, 3, 7, 5, 8, 9, 1]
print("The elements of the array before sorting are:")
print(array)
timsort(array)
print("The elements of the array after sorting are:")
print(array)Output:
In the above program, we are defining a function to find the minimum length of each run. Then we are defining the insertion sort function to sort the elements of each run. Then we are defining the merge sort function to merge each sorted run to a single sorted array. Then we are defining the timsort function, which divides each array into blocks called run and uses the insertion sort and merge sort function to sort the elements of the given array.
Recommended Articles
This is a guide to Timsort Python. Here we discuss the introduction, working of timsort algorithm in python and examples, respectively. You may also have a look at the following articles to learn more –
