# Function to do insertion sort
def insertionSort(arr):

	# Traverse through 1 to len(arr)
	for i in range(1, len(arr)):

		key = arr[i]

		# Move elements of arr[0..i-1], that are
		# greater than key, to one position ahead
		# of their current position
		j = i-1
		while j >= 0 and key < arr[j] :
				arr[j + 1] = arr[j]
				j -= 1
		arr[j + 1] = key


# Driver code to test above
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
for i in range(len(arr)):
	print ("% d" % arr[i])
Copy

def binary_search(arr, val, start, end):
	
	# we need to distinguish whether we
	# should insert before or after the
	# left boundary. imagine [0] is the last
	# step of the binary search and we need
	# to decide where to insert -1
	if start == end:
		if arr[start] > val:
			return start
		else:
			return start+1

	# this occurs if we are moving
	# beyond left's boundary meaning
	# the left boundary is the least
	# position to find a number greater than val
	if start > end:
		return start

	mid = (start+end)//2
	if arr[mid] < val:
		return binary_search(arr, val, mid+1, end)
	elif arr[mid] > val:
		return binary_search(arr, val, start, mid-1)
	else:
		return mid

def insertion_sort(arr):
	for i in range(1, len(arr)):
		val = arr[i]
		j = binary_search(arr, val, 0, i-1)
		arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]
	return arr

print("Sorted array:")
print(insertion_sort([37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54]))

Copy

this is faster and will result in a better algorithm but its not significant improvement cause the power of n remains 2 but coefficient is less.
we know the power of n is the most important thing for example an algorithm with complexity equal to is a lot slower than a algorithm with complexity .

session 1