The basic idea of insertion sort is that in each iteration, we remove a data point from the data structure we have and then insert it into its right position. That is why we call this the insertion sort algorithm. In the first iteration, we select the two data points and sort them. Then, we expand our selection and select the third data point and find its correct position, based on its value. The algorithm progresses until all the data points are moved to their correct positions. This process is shown in the following diagram:

The insertion sort algorithm can be coded in Python as follows:

def InsertionSort(list):        
    for i in range(1, len(list)):             
        j = i-1             
        element_next = list[i]             
                    
        while (list[j] > element_next) and (j >= 0):                 
            list[j+1] = list[j]                 
            j=j-1                 
        list[j+1] = element_next
    return list

Note that in the main loop, we iterate throughout all of the list. In each iteration, the two adjacent elements are list[j] (the current element) and list[i] (the next element).

In list[j] > element_next and j >= 0, we compare the current element with the next element.

Let's use this code to sort an array:

Let's look at the performance of the insertion sort algorithm.

It's obvious from the description of the algorithm that if the data structure is already sorted, insertion sort will perform very fast. In fact, if the data structure is sorted, then the insertion sort will have a linear running time; that is, O(n). The worst case is when each of the inner loops has to move all the elements in the list. If the inner loop is defined by i, the worst-case performance of the insertion sort algorithm is given by the following:

The total number of passes is shown in the following diagram:

In general, insertion can be used on small data structures. For larger data structures, insertion sort is not recommended due to quadratic average performance.