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...