Insertion Sort
More notes coming soon!

For each item in the unsorted input sequence, insert into the correct position in the sorted output sequence.

A naïve solution involves creation of a separate data structure.

Memory efficient version swaps items onebyone towards the left until they land in the right place. The invariant for this type of insertion sort is that every item to the left of position $i$ is in sorted order, and everything to the right has not yet been examined. Every swap fixes exactly one inversion.
Example
Complexity

In the best case, insertion sort takes $\Theta(N)$ time. In the worst case, $\Theta(N^2)$ time. More generally, runtime is no worse than the number of inversions.

Insertion sort is very fast for arrays that are almost sorted, i.e. that have $\Theta(N)$ inversions. It is also fastest for small $N$ (roughly $N < 15$).