Kodeclik Blog

Insertion Sort Primer

What is sorting?

We are given an array of elements, e.g., numbers, and we desire to put them in order, either increasing or decreasing order. Sorting is important in many areas. For instance, Google needs to sort websites according to relevance to your query. Google Maps sorts routes according to distance or time.

How does insertion sort work?

Insertion sort is one of the easily understood sorting algorithms because we practice it in real life! It is similar to how we sort a pack of cards in our hand.

Given a sequence of cards, we scan it from left to right. When we find a mispositioned card, we insert it in its rightful location and continue to scan for more mispositioned cards. Insertion sort codifies this idea in an algorithm.

Below is a simple illustration of how insertion sort works. We are given the array [35, 67, 12, 95, 21] and desire to sort it in increasing order, so that 12 becomes the first element and 95 becomes the last element. In other words, the array should become [12, 21, 35, 67, 95]. We will show how insertion sort works by showing the first few steps.

Insertion sort scans the array from left to right. There is nothing to do for the first element (i.e., 35) because it is the first element encountered and there is no basis to conclude if it is in the right position or not. Therefore the algorithm moves onto the second element, i.e., 67. This too appears to be in its rightful position (w.r.t. 35) so again nothing to be done.

12 is the first element that appears to be out of order. We now must insert it into its rightful position (among the elements before it). In this case it needs to be positioned before 35 and both 35 and 67 needs to be pushed to the right by one position.

Moving on, 95 seems to be okay. But 21 is again out of order. We move 21 to its rightful location. This requires all elements except 12 to be shifted to the right by one step. At the end of this step, there are no more elements to be processed and thus the array is sorted.

Note that after processing each element, all elements till that element are in their rightful location w.r.t. each other.

How efficient is insertion sort?

Like bubble sort, insertion sort is not a very efficient algorithm. Formally, in computer science terminology, bubble sort is considered to have O(n^2) worst case time complexity, meaning as the size of the array increases the time taken to sort it increases not linearly, but quadratically. It is easy to see that this worst case happens when the array is in exactly the reverse sorted order.

What are the advantages of insertion sort?

There are some situations when insertion sort is very advantageous. If you are sorting elements as they arrive in real time (as opposed to having all of them in memory) insertion sort is a very attractive algorithm.

Insertion sort is also part of a class of “stable sorting” algorithms. This means if you present the algorithm with two equal-valued elements, their relative positions do not change over the run of the algorithm. This is an important feature to have in many domains.

How does insertion sort relate to bubble sort?

Both bubble sort and insertion sort have the same worst case time performance. Both of them are part of the “comparison sorting” family of algorithms, meaning the algorithms operate by making comparisons between elements.

By the end of the ith iteration, the largest “i” elements are in their correct (rightmost) location in bubble sort. Whereas, in insertion sort, by the end of the ith iteration, the smallest “i” elements are in their correct location(s).

In practice, insertion sort will be faster than bubble sort because bubble sort makes a lot of wasted swaps in order to bring an element to its correct position.

Another difference between bubble sort and insertion sort can be seen when the array becomes sorted. Bubble sort will perform one wasted sweep in order to detect that the array is sorted whereas insertion sort knows that it is sorted the moment it gets sorted.

How can we code insertion sort in Python?

Here is a sample implementation of an insertion sort function in Python.

def insertionsort(array):
  shifts = 0;
  for i in range(len(array)-1):

    # we are trying to position element in 
    # array[i+1] by comparing it to every
    # element from array[0] to array[i]
    current_element = array[i+1]

    # cycle through every element from 0 to i
    # starting from the right
    compare_with_index = i
    while (compare_with_index >= 0 and 
      current_element < array[compare_with_index]):

      # start moving elements to the right
      shifts += 1;
      array[compare_with_index+1] = array[compare_with_index]
      compare_with_index -= 1;
    
    # now position the element correctly
    array[compare_with_index+1] = current_element
  return(shifts)

Note that we are giving an "array" as input to the insertion sort function. There are two nested loops, a while inside a for loop and the ranges are carefully controlled.

We also have a variable called “shifts” that counts the number of shifts to the right. Also note that we are using Python's call-by-object-reference style that updates the array when passed into the function.

We can invoke this function as follows:

my_array = [35, 67, 12, 95, 21];
print("array before sorting: ",my_array)
shifts = insertionsort(my_array)
print("array after sorting: ",my_array)
print("It took",shifts,"shifts to the right.")

The output is:

array before sorting:  [35, 67, 12, 95, 21]
array after sorting:  [12, 21, 35, 67, 95]
It took 5 shifts to the right.

What happens if we give it an already sorted list, such as [10,29,30,45,50,89]?

array before sorting:  [10, 29, 30, 45, 50, 89]
array after sorting:  [10, 29, 30, 45, 50, 89]
It took 0 shifts to the right.

Note that the algorithm did not need to do any shifts at all.

In this blogpost we have learnt about the insertion sort algorithm and how to code it in Python. Learn about a different sorting algorithm in this blog post about bubble sort and in this blog post about merge sort. Also learn about Python's enumerate() functionality.

Want to learn Python with us? Sign up for 1:1 or small group classes.