# Insertion sort

## Algorithm

```
def insertion(a):
"""
Implements the insertion sort algorithm
"""
for i in range(0, len(a) - 1):
if a[i] < a[i+1]:
continue
insert_index = i+1
insert_element = a[i+1]
for j in range(i,-1,-1):
if a[j+1] < a[j]:
temp = a[j+1]
a[j+1] = a[j]
a[j] = temp
return a
def insertion2(a):
"""
Implements the insertion sort algorithm.
"""
if len(a) == 1:
return a
for i in range(1, len(a)):
if a[i] > a[i-1]:
continue
for j in range(i,0,-1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
return a
```

## Key concepts

- Insert the current element where it belongs.
- It will be inserted in an already sorted subarray.
- Start looking for a place to insert the element from the current index and move towards the beginning of the array.

## Step by step

```
array = [1,0,3,4,2,5]
i = 0
a[0] < a[1] | 1 < 0 | False
insert_index = 1
insert_element = 0
j = 0
a[1] < a[0] | 0 < 1 | True
temp = a[1] | temp = 0
a[1] = a[0] | a[1] = 1
a[0] = temp | a[0] = 0
array = [0,1,3,4,2,5]
i = 1
a[1] < a[2] | True
array = [0,1,3,4,2,5]
i = 2
a[2] < a[3] | 3 < 4 | True
array = [0,1,3,4,2,5]
i = 3
a[3] < a[4] | 4 < 2 | False
insert_index = 4
insert_element = 2
j = 3
a[4] < a[3] | 2 < 4 | True
temp = a[4] | temp = 2
a[4] = a[3] | a[4] = 4
a[3] = temp | a[3] = 2
array = [0,1,3,2,4,5]
j = 2
a[3] < a[2] | 2 < 3 | True
temp = a[3] | temp = 2
a[3] = a[2] | a[3] = 3
a[2] = temp | a[2] = 2
array = [0,1,2,3,4,5]
j = 1
a[2] < a[1] | 2 < 1 | False
j = 0
a[1] < a[0] | 1 < 0 | False
array = [0,1,2,3,4,5]
i = 4
a[4] < a[5] | 4 < 5 | True
```

## Complexity analysis

### Time

For each element of the array, we compare it with all the previous elements of the array. This gives us 1 in the best case and N in the worst case. This gives us N/2 in the average case. So O(N) = N (N/2) = N²/2.

One could further argue that half of the times (for the average case) the elements we are comparing are already sorted and thus there is no need to do the insertion part of the algorithm with the N²/2 cost. In that case, we can write the computational cost as: O(N) = (1/2)(N²/2) = (N²/4)

### Space

We use the same array that is passed as argument and a few more variables, so the cost is: O(N) = N + K ≈ N.

## Use cases

This algorithm is specially useful for arrays that are:

- Partially sorted
- Tiny

Examples:

- Array where each entry is not far from its final position
- Arrays in which only a few entries are not sorted
- Arrays that are a concatenation of two sorted arrays