Implement an insertion sorting algorithm but do it in place

Implement an insertion sorting algorithm, but do it in place. That means do not introduce a second list svals, and this means you will have to perform all your operations on the list a user would input to be sorted. As a hint, if the list you are sorting is given by vals, then I found the line vals.insert(kk, vals.pop(jj)) very useful. Provide a test case to show your method works.

Solution

Implementaion of insertion sort without introducing a secong list.

def insertion(l):
for index in range(1,len(l)):

value = l[index]
pos = index

while pos>0 and l[pos-1]>value:
l[pos]=l[pos-1]
pos = pos-1

l[pos]=value

vals = [54,2,93,17,77,31,44,55,20]
insertion(vals)
print(vals)