The insertion sort is another algorithm that makes it possible to sort a single-dimensional array in a simple way, as shown in the following diagram. Similarly, as in the case of the selection sort, the array is divided into two parts, namely sorted and unsorted. However, at the beginning, the first element is included in the sorted part. In each iteration, the algorithm takes the first element from the unsorted part and places it in a suitable location within the sorted part, to leave the sorted part in the correct order. Such operations are repeated until the unsorted part is empty.
Let's take a look at an example of sorting an array with nine elements (-11, 12, -42, 0, 1, 90, 68, 6, -9) using the insertion sort, which is ...
