Insertion sort is a sorting algorithm that is similar to arranging a hand of poker cards. This sorting algorithm will also divide the list into a sorted and unsorted sublist in the sorting process. For clarity, we pick an item as a reference, then go through the sorted sublist and find the correct position based on performing a comparison. This process is repeated until all the items are sorted, which means that we have to iterate through all of the array's elements.
Let's use our previous array {43, 21, 26, 38, 17, 30} and then perform an insertion sort algorithm on it. First, we set array[0] as the sorted sublist, so we pick array[1] as the reference. Now, we compare the reference item, which is 21, with the sorted sublist. See the following diagram:
Since 21 is lower than 43, 43 will be shifted to array[1] and since no more items are in the sorted sublist, 21 is put into array[0]. Now, array[0] and array[1] are in the sorted sublist, as we can see in the following diagram...