Insertion Sort Algorithm in Python

Insertion sort algorithm works by comparing two elements at a time and swapping them if required. Up till this, it is similar to the bubble sort algorithm. However unlike bubble sort algorithm which iterates through the entire loop multiple times swapping just two elements at a time, insertion sort keeps swapping elements at one end of the list and moves to the next element only when the list is sorted up to elements before this new element.

Here’s the code in Python.

def insertion_sort(lst):
    for i in range(1, len(lst)):
        j = i - 1
        while (j >= 0) and (s[j] > lst[i]):
            lst[j+1] = lst[j]
            j = j - 1
        lst[j+1] = lst[i]

Insertion sort is advantageous than bubble sort in that it makes only fewer comparisons unless the list to be sorted is totally backwards where both algorithms would take equal number of steps to complete.

Insertion sort method is a great way to insert new elements into a sorted list and this is how it is most commonly used in day to day programming.