# 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 > array`, so `array` should appear before `array`. Hence we swap them to adjust their positions.

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

Iteration 3:
In this case, `array < array`, so we swap them so that `array=7` and `array=1`. Now, `array` which is `1` is again less than `array`, so we swap them again such that `array=1` and `array=5`. Now also, `array > array`, so we swap these elements such that `array=1` and `array=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]
```