57# array[0...n-1] (similar to merge sort)
58
59
60def tim_sort(arr):61    n = len(arr)
62    # Sort individual subarrays of size RUN
63    for i in range(0, n, RUN):

18
19
20# merge function merges the sorted runs
21def merge(arr, l, m, r):22    # original array is broken in two parts
23    # left and right array
24    len1, len2 = m - l + 1, r - m

 5# to right index which is of size atmost RUN
 6
 7
 8def insertion_sort(arr, left, right): 9    for i in range(left + 1, right + 1):
10        temp = arr[i]
11        j = i - 1

 1# Python program to implement stooge sort
 2def stooge_sort(arr, first=0, last=None): 3    if last is None:
 4        last = len(arr) - 1
 5    if first >= last:

 1# Python3 program for implementation of Shell Sort
 2
 3
 4def shell_sort(arr): 5    # Start with a big gap, then reduce the gap
 6    n = len(arr)
 7    gap = n // 2