# the worst time complexity is O(n^2), the best is O(n)
def insertSort(a):
# from the second element
for i in range(1, len(a)):
key = a[i]
j = i
# if has any element bigger than it then shift to right one by one.
# because all elements on the left have been sorted ,
# so if any element smaller than or equal to it,
# all element from the left will not bigger than it any more.
while j > 0 and a[j - 1] > key:
a[j] = a[j - 1]
j -= 1
# put key to the current place
a[j] = key
if __name__ == "__main__":
a = [2, 4, 1, 6, 3, 9, 10, 5, 7, 8, 3]
insertSort(a)
print(a)