Sort

Insertion Sort

The idea of an insertion sort is this: initially, only the first item is considered sorted. Then, for each item in the sequence, we "insert" that item into the sorted list by swapping it with the item before it until the item is smaller than the current item.