Insertion sort is a simple sorting algorithm that builds the final sorted list one item at a time. It is much less efficient.

x=[98,67,85,67,85,47]

>>> def insertion_sort(x):

for i in range(1,len(x)):

j=i

while j>0 and x[j]<x[j-1]:

x[j],x[j-1]=x[j-1],x[j]

j=j-1

return k

>>> insertion_sort(x)

[6, 7, 12, 32, 43, 45]

**Best-case performance**: O(n) comparisons,**Average performance**:О(n2) comparisons**Worst-case space complexity**:О(n) total**Example:**x=[98,67,85,67,85,47]

>>> def insertion_sort(x):

for i in range(1,len(x)):

j=i

while j>0 and x[j]<x[j-1]:

x[j],x[j-1]=x[j-1],x[j]

j=j-1

return k

>>> insertion_sort(x)

[6, 7, 12, 32, 43, 45]