Insertion Sort

Insertion sort builds a sorted portion of the array one element at a time.

It begins by treating the first element as a sorted list. Then, it takes the next element and inserts it into the correct position within the sorted portion. This process continues until every element has been inserted.

For example, consider the following array.

Insertion sort proceeds like this:

1. Start with 7 as the sorted portion.
2. Insert 3 before 7.
3. Insert 9 after 7.
4. Insert 1 at the beginning.
5. Insert 5 between 3 and 7.

The final result is:

Because insertion sort grows the sorted portion one element at a time, it works well for small collections or collections that are already mostly sorted.