## 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(n^{2}), and best case complexity is O(n).