So far, we have seen two comparison-based sorting algorithms. Now, we will explore another sorting algorithm that is somewhat efficient compared to the previous two. We are talking about the insertion sort. It has the simplest implementation compared to the other two sorting algorithms we have just seen. If the number of items is smaller, insertion sort works better than bubble sort and selection sort. If the data set is large, then it becomes inefficient, like bubble sort. Since the swapping is almost linear for insertion sort, it is recommended that you use insertion sort instead of bubble sort and selection sort.
As the name suggests, insertion sort works on the principle of inserting the number to its correct place on the left-hand side. It starts from the second item of the array and checks whether the items that are left to it are smaller than the current value or not. If so, it shifts the item and stores the smaller item in its correct position. Then, it moves to the next item, and the same principle continues until the full array is sorted. The pseudocode for insertion sort looks like this:
procedure insertionSort( A : list of sortable items )
n = length(A)
for i = 1 to n inclusive do
key = A[i]
j = i - 1
while j >= 0 and A[j] > key do
A[j+1] = A[j]
j--
end while
A[j+1] = key
end for
end procedure
If we consider our previous list of numbers used for bubble sort and selection sort, then we will have the following scenario for which we must do insertion sort.
The elements of our array were: 20, 45, 93, 67, 10, 97, 52, 88, 33, 92.
Let's start with the second item, which is 45. Now, we will start from the first item to the left of 45 and go to the beginning of the array to see whether there is a value greater than 45 on the left. As there is only 20, no insertion is required as the item so far is sorted until the second element (20,45). Now, we will move our pointer to 93, and it starts again, comparing left of the array starting from 45 and search if the value is bigger. Since 45 is not bigger than 93, it stops there, as previously, we concluded that the first two items are already sorted. Now, we have the first three items (20, 45, 93) sorted. Next, we have 67, and we start again by comparing from the left of the numbers. The first number to the left is 93, which is bigger, so it has to move one place. We move 93 to the position that was held by 67. Then, we move to the next item to the left of it, which is 45. 45 is smaller than 67, and no further comparison is required. Now, we will insert 67 at the position that was held by 93 and 93 will have to be moved to 67's position. This continues until the full array is sorted. This image illustrates the full sorting process using insertion sort at each step:
