Updated May 16, 2023
Introduction to Tim Sort
Tim Peters introduced Tim sort as a stable sorting algorithm for Python language in 2001, that comprises of insertion sort and merge sort to enhance the performance of sorting by breaking the array of elements into blocks of size 32 or 64(depending on array size) known as Run and then perform sorting on these run using insertion sort since insertion sort performs well when the array size is less, and further merge them using merge sort since merge sort performs its best when the number of elements in the array is of power of 2. In this topic, we are going to learn about Tim Sort.
How to Perform Tim Sort?
Tim Sort is the fastest sorting algorithm that uses 2 algorithms to work in their best cases.
Tim Sort works on the fact that performing merge sort on small sorted chunks makes it performance fast. Thus here, our job is to split the array into different runs of the same size and sort them using insertion Sort.
For eg – [33,45, 21,67,89,15, 72, 234, 109]
Part #1
Here we will split this array into run of size = 3
3
Now we will perform insertion sort on each of these runs.
[33,45,21] -> [33,45,21] ->[33,21,45] [67,89,15] -> [67,89,15] -> [67,15,89] ->[15,67,89] [72,234,109] -> [72,234,109] -> [72,109,234]Resulting Array ->[33,21,45,15,67,89,72,109,234]
Complexity– Insertion Sort requires binary Searches for the right place for a new element + the shift of all the elements to the right. Thus in case, the number of elements in the array is n then,
Binary Search complexity = log(n), and since it is performed for each element of the array, thus the number of comparisons = nlog(n)
Number of Shifts = 1+2+3….n-1 elements = (n-1)*n/2 = O(n2)
Cost to perform insertion sort = nlog(n) comparisons + n2shifts, where Operating system is more optimized to perform shifts and enhance the performance.
For the best performance, we are required to keep the run size at the power of 2, and a minimum size of =32, and a maximum size of 64 elements.
Part #2
Now once we have run with sorted elements, we will perform mergeSort on them.
Performing merge Sort requires extra space for an array to store the elements for comparisons, which in many cases sum of the left and right array, i.e., 6, but here we are going to take an array of size = min(size of leftArray, size of rightArray) which reduces the space required.
Now we will use the below algorithm to perform merge Sort on first 2 runs
[33,21,45, 15, 67,89, 72,109,234]Step 1 – Initialize a new array Arr2 of size = 3, copy the elements of the 2nd run in new Array 2, and shifting the elements in the Arr1 to the right by 3 positions.
Step 2 – Comparing the elements in both the arrays and start filling Array1.
[0,0,0,33,21,45] [15,67,89] – > Since 15<33 ->[15,0,0,33,21,45] [15,0,0,33,21,45] [15,67,89] -> Since 33<67 ->[15,33,0,33,21,45] [15,33,0,33,21,45] [15,67,89] -> 21<67 ->[15,33,21,33,21,45] [15,33,21,33,21,45] [15,67,89] ->45<67 -> [15,33,21,45,21,45]Step 3 – Copy the rest of the elements in the array that have not been visited
[15,33,21,45,67,89]Since less extra space is used thus it is an in-place sorting algorithm, and in case 2 elements with the same value are compared, the value with a lower index is taken first, thus making the algorithm more stable.
Repeat above 3 steps for next run also with Arr1 = [15,33,21,45,67,89,72,109,234] Arr2 = [72,109,234]
And the Resultant array = >[15,33,21, 45,67,72,89, 109,234]
Complexity of merge Sort = Cm.nlog(n-x) , x is the number of levels reduced in mergeSort thus our target must to increase x and Cmis the number of space required that we reduced to half.
Optimal Solution to perform Merge on runs
For performing merge sort on these runs in a more efficient manner, put them in the stack(runs) and will be pulled recursively.
[33,21,45] [15,67,89] [72,109,234]Algorithm
while(runs.length>=2) :
If(runs[2].length > runs[0].length + runs[1].length{
If(runs[0].length > runs[1].length){
Merge(runs[0],runs[1])
} else : break;
}
else : merge(runs[1],min(runs[0],runs[2])
Example
RUNLENGTH = 32
def iSort(myArr, leftIndex, rightIndex):
for x in range(leftIndex + 1, rightIndex+1):
temp1 = myArr[x]
y = x - 1
while myArr[y] > temp1 and y >= leftIndex:
myArr[y+1] = myArr[y]
y -= 1
myArr[y+1] = temp1
def mergeArray(myarr, lIndex, mid, rIndex):
l1, l2 = mid - lIndex + 1, rIndex - mid
leftArr, rightArr = [], []
for i in range(0, l1):
leftArr.append(myarr[l + i])
for i in range(0, l2):
rightArr.append(myarr[mid + 1 + i])
i, j, k = 0, 0, l
while i < l1 and j < l2:
if leftArr[i] <= rightArr[j]:
arr[k] = leftArr[i]
i += 1
else:
arr[k] = rightArr[j]
j += 1
k += 1
while i < l1:
myarr[k] = leftArr[i]
k += 1
i += 1
while j < l2:
myarr[k] = rightArr[j]
k += 1
j += 1
def timSorting(myArr, num):
for i in range(0, num, RUNLENGTH):
iSort(myArr, i, min((i+31), (num-1)))
size = RUNLENGTH
while size < num:
for left in range(0, num, 2*size):
mid = left + size - 1
right = min((left + 2*size - 1), (num-1))
mergeArray(myArr, left, mid, right)
size = 2*size
if __name__ == "__main__":
myArr = [33,45, 21,67,89,15, 72, 234, 109]
num = len(myArr)
print("Array elements before sorting is")
for i in range(0, num):
print(myArr[i], end = " ")
print()
timSorting(myArr, num)
print()
print("Array elements after sorting is")
for i in range(0, num):
print(myArr[i], end = " ")
print()
Output:
Conclusion – Timm Sort
Tim sort is a mechanism to perform sorting on an array of elements by breaking them into runs up to a size of 32 or 64 and then sort them using insertion sort that is considered best when the array size is small and then merging all runs in sorted order using merge sort since it works best with chunks of sorted elements bringing the complexity of O(n log n) time.
Recommended Articles
This is a guide to Timm Sort. Here we discuss How to perform Tim Sort along with the 2 algorithms to work in their best cases. You may also have a look at the following articles to learn more –
