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 is in sorted order, and everything to the right has not yet been examined. Every swap fixes exactly one inversion.
In the best case, insertion sort takes time. In the worst case, 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 inversions. It is also fastest for small (roughly ).