Insertion sort is a sorting algorithm that builds a final sorted array one item at a time by comparisons. It iterates across a list taking one element at a time and inserting it into the leftmost portion of the list at it’s sorted location.

```
INPUT: a₁, a₂, ..., aₙ as A
FOR i ← 2 to n
j ← i
WHILE j > 1 AND A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
```

Worst | Average | Best | |
---|---|---|---|

Time |
\(O(n^2)\) | \(O(n^2)\) | \(O(n)\) |

Space |
\(O(n)\) |