time complexity of shellsort is on2 in the above implementation gap is reduce by half in every iteration here are many other ways to reduce gap which lead to better time complexity see this for more details start with a big gap then reduce the gap do a gapped insertion sort for this gap size the first gap elements a0 gap1 are already in gapped order keep adding one more element until the entire array is gap sorted add ai to the elements that have been gap sorted save ai in temp and make a hole at position i shift earlier gapsorted elements up until the correct location for ai is found put temp the original ai in its correct location start with a big gap then reduce the gap do a gapped insertion sort for this gap size the first gap elements a 0 gap 1 are already in gapped order keep adding one more element until the entire array is gap sorted add a i to the elements that have been gap sorted save a i in temp and make a hole at position i shift earlier gap sorted elements up until the correct location for a i is found put temp the original a i in its correct location
def shell_sort(arr):

    
    n = len(arr)
    gap = int(n / 2)

    
    
    
    
    while gap > 0:

        for i in range(gap, n):

            
            
            temp = arr[i]

            
            
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            
            arr[j] = temp
        gap = int(gap / 2)

arr = [ 12, 34, 54, 2, 3]

shell_sort(arr)
print(arr)