# Python - Insertion Sort Algorithm Implementation

Insertion sort algorithm - In the last couple of articles, we studied Bubble sort and Selection sort algorithms. In this article, we will learn about another sorting algorithm - Insertion sort. Just like Bubble sort and selection sort, time complexity of this algorithm is O(n^2) and space complexity being O(1).

#### Selection Sort Algorithm

```1. First element i.e. element at index 0 is always sorted and is the part of sorted sub-list
2. Select next element
3. Compare it with all elements in sorted sub-list
4. If the value of the element is smaller, swap it with the element(s) in sorted sub-list
5. Continue till we get an element from sorted sub-list which is smaller than the element
6. Insert the element in the sorted sub-list
7. Get the next element
7. Repeat this process for selected element
```

#### Example

Consider the following list-

Initially, the first element in the list is already sorted. Hence we add that to sorted sub-list identified with green color.

Iteration 1:
Compare element at index 1 with the elements in sorted sub-list and insert at appropriate location. Here, `array[0] > array[1]`, so `array[1]` should appear before `array[0]`. Hence we swap them to adjust their positions.

Iteration 2:
In this case, `array[2] > array[1]`, hence nothing needs to be required as it is already at appropriate position.

Iteration 3:
In this case, `array[3] < array[2]`, so we swap them so that `array[3]=7` and `array[2]=1`. Now, `array[2]` which is `1` is again less than `array[1]`, so we swap them again such that `array[1]=1` and `array[2]=5`. Now also, `array[1] > array[0]`, so we swap these elements such that `array[0]=1` and `array[1]=3` and we are done.

Iteration 4:

Iteration 5:

Iteration 6:

Iteration 7:

#### Python Implementation:

```def insertion_sort(array):

n = len(array)

for i in range(1, n):
j = i
current = array[j]
while j > 0 and array[j-1] > current:
array[j] = array[j-1]
j -= 1
array[j] = current

my_array = [5, 3, 7, 1,4, 8, 2, 6]
insertion_sort(my_array)
print my_array
```

Output:

```[1, 2, 3, 4, 5, 6, 7, 8]
```