Insertion Sort in Python
Insertion sort examine the previously sorted sub-array and insert an element at its proper position.
If you have an array a[0], a[1], a[2], a[3],……….a[n].
Then in insertion sort a[0] trivially sorted sub-array.
Again compare a[0] to a[1] and if a[0]> a[1] exchange it.
Now sub-array a[0],a[1] is sorted again compare a[2] with sub-array a[0],a[1] and insert it into proper position.
Now sub-array a[0],a[1],[2] is sorted again compare a[3] with sub-array a[0],a[1],[2] and insert it into proper position.
This process will go on until array a[] is sorted.
See a numerical example, then your understanding will be more clear.
Insertion Sort in Python
a=[15, 23, 40, 10, 3, 35, 25, 5, 30, 33]
for i in range(len(a)):
t=a[i]
j=i-1
while t < a[j] and j >= 0:
a[j+1]=a[j]
j=j-1
a[j+1]=t
print(a)
Time complexity of Insertion Sort
The average and worst case complexities of insertion sort is O(n2), and best case complexity is O(n).