Insertion sort is a popular shorting algorithm, similar to selection sort the unsorted list or array is divided into to two parts, left part being sorted which is initially empty and the right part being unsorted which at the very beginning is the entire list.

At each iteration element from the unsorted list is inserted at the appropriate position in the sorted part. This process continues until the entire list is sorted. Basically, we are iterating over the element of the sorted list until the correct position is found.

Since the items of the unsorted part are continuously inserted at appropriate positions at the sorted list therefore named Insertion sort.

Insertion Sort Program In Python

def instertion_sort(seq):

    for slice_end in range(len(seq)):
        pos = slice_end
        # inserting elements at correct position
        while pos > 0 and seq[pos] < seq[pos - 1]:
            (seq[pos], seq[pos - 1]) = (seq[pos - 1], seq[pos])
            pos = pos - 1


# test input
l = [54, 26, 93, 17, 77, 31, 44, 55, 20]
instertion_sort(l)
print(l)

Output:

[17, 20, 26, 31, 44, 54, 55, 77, 93]

In the above function outer for loop is iterating over every element of the list from index 0 to the end of the list, the inner while loop swaps the values and inserts them to their appropriate positions this keeps on continuing until the entire list is sorted.