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 one-by-one 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

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$ ).