Insertion Sort

Insertion sort traverses the array and inserts each element into its correct position in the already sorted portion. Then, it repeats for the remaining part of the array: it searches for the smallest element among the not yet sorted elements, and exchanges it with the first free position, and so on until everything is sorted.

In summary:

• At each step, we select the smallest remaining element,
• We place it in its correct position,
• Then we continue with the rest of the array.