Insertion sort is one of the most classic type of sorting algorithm, you take every element one at a time and place it where he belongs and repeat the operation till the end.
This isn't the most efficient way to sort but he is quite useful for small sets and he is really simple to implements.
| Condition | Time complexity | Space Complexity |
|---|---|---|
| Best | O(n) | |
| Average | O(n^2) | |
| Worst | O(n^2) | O(n) |