## Definition of insertion sort

Insertion sort is a type of sorting algorithms that works like *the process of sorting playing cards*, it **divides** the array into two parts, part of *sorted numbers* and other of **unsorted numbers**, the numbers that are in the wrong order ( *numbers that exist in the unsorted part* ) are inserted to the sorted part in the correct position.

## Time and Space complexity of insertion sort

time Complexity | Space Complexity |
---|---|

O(n^{2}) |
O(1) |

## Algorithm explanation using an example

let's suppose we have an unsorted array [**7**,*4,12,3*],

the sorted part is 7 (bold styling), the unsorted part is from 4 to 3 (italic styling).

- (4 < 7) that's why we will insert 4 in the sorted part before 7
so the array will be [
**4,7**,*12,3*] - (12 > 7) therefore will keep it in the same position so the array will be [
**4,7,12**,*3*] - since 3 is smaller than 12,7 and 4, it will be in the first position, so the final array is [
**3,4,7,12**]

## Implementation of insertion sort algorithm using python

if you're not familiar with python, you can find the implementaion of insertion sort algorithm in other programming languages:

=> python:

```
def insertionSort(items: list) -> list:
"""
[ name ] => insertion sort
[ type ] => sorting algorithms
[ time complexity ] => O(n^2)
[ space complexity ]=> O(1)
[ params ] => (items) list to sort
[ return ] => sorted list
[ code reference link ] => ("https://www.geeksforgeeks.org/insertion-sort/")
"""
for i in range(1, len(items)):
key = items[i]
j = i - 1
while j >= 0 and key < items[j] :
items[j + 1] = items[j]
j -= 1
items[j + 1] = key
return array
```

## References and useful resources

- https://www.geeksforgeeks.org/insertion-sort/
- https://www.tutorialspoint.com/data_structures_algorithms/insertion_sort_algorithm.htm
- https://www.youtube.com/watch?v=JecAk1FAOck
- https://www.youtube.com/watch?v=OGzPmgsI-pQ
- https://www.youtube.com/watch?v=JU767SDMDvA

Special thanks to geeksforgeeks.

Have a good day :)

#day_9

## Discussion (0)