# Python3 program for implementation of Shell Sort

def shellSort(arr):
	gap = len(arr) // 2 # initialize the gap

	while gap > 0:
		i = 0
		j = gap
		
		# check the array in from left to right
		# till the last possible index of j
		while j < len(arr):
	
			if arr[i] >arr[j]:
				arr[i],arr[j] = arr[j],arr[i]
			
			i += 1
			j += 1
		
			# now, we look back from ith index to the left
			# we swap the values which are not in the right order.
			k = i
			while k - gap > -1:

				if arr[k - gap] > arr[k]:
					arr[k-gap],arr[k] = arr[k],arr[k-gap]
				k -= 1

		gap //= 2


# driver to check the code
arr2 = [12, 34, 54, 2, 3]
print("input array:",arr2)

shellSort(arr2)
print("sorted array",arr2)