Insertion Sort in Python

In this tutorial, we will learn about insertion sort in Python, a sorting algorithm that works very similar to how we sort things in real life. Let’s get started.

The Insertion Sort Algorithm

If you have a set of cards numbered 1 to 10 which are shuffled, and you’re asked to sort them, you will probably pick up each card one by one and insert them in another sorted pile in their correct position.

Much like the way we tend to sort things, Insertion Sort maintains a sorted section in the given sequence, takes one item from the unsorted section, and inserts it into its correct position in the sorted section.

In the beginning, there is just one element in the sorted section which is the very first one (The sorted section is at the beginning of the list).

We keep track of where the unsorted section starts using an index, and the unsorted section starts from the second element, so the index needs to be 1 (In the case of Python).

Now, we take the first element from the unsorted section (The element at the unsorted index) and try to find its position in the sorted section.

We do so by consecutively comparing it to each element in the sorted section until we find an element that is smaller (If the list is ascending) or larger (If the list is descending) than the new element.

Next, we insert it at the position and move all the sorted elements once to accommodate the new element. The process is repeated until the entire array is sorted.

Insertion Sort in Python

The algorithm in Python will look something like this:

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

Notice that the function takes in a list and performs the sorting in-place. However, it is fairly simple to alter the algorithm to return a sorted list instead.

Understanding the Insertion Sort algorithm

Let us try to run this algorithm on an example to see how it works.

• Say, the given list is: 12, 16, 11, 10, 14, 13.
• Size of the given list: 6
• Sorting in increasing order.

• Now, i will go from 1 to 5, and so, all the elements from 16 till 13 will be inserted in their correct position.
• Inside the first loop, j will go from i - 1 to 0, so it is responsible for finding the correct position. j will move back in the list along with the selected item as it tries to find its correct position.
• Further inside, we will compare the item at j with the selected item (which will always be at j + 1), and if the item at j is greater, the positions j and j + 1 will be swapped, and the item will move backward.
• After this j will decrease by 1, and it will make sure that the selected item is always at the position j + 1.
• Finally, the item at j will no longer be greater than the selected item, and the selected item will have moved to its correct position, and it will end the inner loop.
• The outer loop will now do the same to the next item.

The changes in the sequence will look something like this:
12, 16, 11, 10, 14, 13
12, 11, 16, 10, 14, 13
11, 12, 16, 10, 14, 13
11, 12, 10, 16, 14, 13
11, 10, 12, 16, 14, 13
10, 11, 12, 16, 14, 13
10, 11, 12, 14, 16, 13
10, 11, 12, 14, 13, 16
10, 11, 12, 13, 14, 16
10, 11, 12, 13, 14, 16

• The items in green show that they are in their correct position in the sorted section.
• The items in red are being sorted as they move left towards their correct position.
• The uncolored items are the unsorted section of the list.

The Output

Running the same list on the algorithm, it will produce the following result:

Conclusion

In this tutorial, we saw how Insertion Sort is very similar to how we sort things in real life, we discussed the algorithm it uses and implemented Insertion sort in Python.

After that, we discussed how the algorithm is working and dry ran the algorithm on an unsorted example. Finally, we verified the dry run using the actual output of the code. Insertion sort, like the Bubble Sort, also has a complexity of O(n²).

So similar to that, if the input size is doubled, the time it takes to execute increases by four times, and if the input is tripled, the time it takes to execute increases by nine times.

This makes the algorithm inefficient for practical use, but it is a very intuitive algorithm to implement.

I hope you enjoyed learning about Insertion Sort and see you in the next tutorial.