Shell Sort

def shell_sort(arr):
    # divide into sub-groups based on the gap
    # then do insertion sort on each sub-group
    # then reduce gap and do it again until tha gap is 1
    n = len(arr)
    # initial gap is the half of the length
    gap = n // 2
    while gap > 0:
        # do insertion sort on each sub-group
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # insertion sort
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        # reduce the gap
        gap //= 2


# Test
arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("After Shell Sort: ", arr)
# After Shell Sort:  [2, 3, 12, 34, 54]