Prerequisites

To learn about Insertion Sort, you must know:

1. Python 3
2. Python data structures - Lists

What is Insertion Sort?

We are in the second tutorial of the sorting series. The previous tutorial talks about Bubble Sort which is a very simple sorting algorithm. If you haven’t read that, you can find it here. Like all sorting algorithms, we consider a list to be sorted only if it is in the ascending order. Descending order is considered the worst unsorted case.

As the name suggests, in Insertion Sort, an element gets compared and inserted into the correct position in the list. To apply this sort, you must consider one part of the list to be sorted and the other to be unsorted. To begin, consider the first element to be the sorted portion and the other elements of the list to be unsorted. Now compare each element from the unsorted portion with the element/s in the sorted portion. Then insert it in the correct position in the sorted part. Remember, the sorted portion of the list remain sorted at all times.

Let us see this using an example, alist = [5,9,1,2,0]

Round 1:

sorted - 5 and unsorted -  9,1,2,0

5<9: nothing happens

alist =  [5,9,1,2,0]

Round 2:

sorted - 5, 9 and unsorted - 1,2,0

1<9: do nothing

1<5: insert 1 before 5

alist = [1,5,9,2,7,0]

Round 3:

sorted -1, 5, 9 and unsorted - 2,0

2<9: do nothing 

2<5: do nothing

2>1: do nothing

insert 2 before 5

alist = [1,2,5,9,0]

Note: even though it is clear for us that 2 is lesser than 5 but greater than 1, the algorithm has no way of knowing this. Hence only after comparing with all the elements in the sorted part, it makes the insertion is the correct place.

Round 4:

sorted -1, 2, 5, 9 and unsorted - 0

0<9: do nothing

0<5: do nothing

0<2: do nothing

0<1: insert 0 before 1

alist = [0,1,2,5,9]

See this animation for better understanding.

How to implement Insertion Sort?

Now that you have a fair understanding of what Insertion Sort is, let us take a look at the algorithm and its code.

Algorithm

1. Consider the first element to be sorted and the rest to be unsorted
2. Compare with the second element:
   1. If the second element< the first element, insert the element in the correct position of the sorted portion
   2. Else, leave it as it is
3. Repeat 1 and 2 until all elements are sorted

NOTE: As the number elements in the sorted portion increases, the new element from the unsorted portion must be compared with all the elements in the sorted list before insertion.

Code

def insertionSort(alist):

   for i in range(1,len(alist)):

       #element to be compared
       current = alist[i]

       #comparing the current element with the sorted portion and swapping
       while i>0 and alist[i-1]>current:
           alist[i] = alist[i-1]
           i = i-1
          alist[i] = current

       #print(alist)

   return alist

print(insertionSort([5,2,1,9,0,4,6]))

Uncomment the print statement to see how the list gets sorted.

Conclusion

Insertion Sort works best with small number of elements. The worst case runtime complexity of Insertion Sort is o(n2) similar to that of Bubble Sort. However, Insertion Sort is considered better than Bubble sort. Explore why and comment below. That’s it for this tutorial. Happy Pythoning!