Insertion sort is a simple algorithm to sort a given array or list of numbers. In insertion sort, in each iteration, we pick up a number starting from the second position and make it the key. Then we compare the key with all the numbers before it and insert it at the right place, where the number before it is less than it and the number after it is greater than it.
And we keep on doing this until the whole array is sorted.
Insertion sort is adaptive, which means it reduces its total number of steps if the given list is partially sorted, hence it increases its efficiency.
Also, it is efficient for smaller data sets but very inefficient for larger lists.
We have a detailed tutorial covering How Insertion Sort Works, and we strongly recommend you go through it to understand the functioning of the insertion sort algorithm, before going over the code below.
We have used the python list for implementing the insertion sorting technique. You can change the code, as you like.
