Insertion Sort Algorithm

Insertion sort is an algorithm used to sort (or order) elements present in a list. It sorts elements present in the list by picking elements from the un-sorted list one by one, and inserts them to a new list at the correct place so as to keep the new list sorted. It is similar to how most people sort playing cards and keep them sorted even after picking and inserting a new card.

(Watch related video for better understanding).

Idea Behind the Algorithm

Insertion sort visits one element at a time from the unsorted list and builds a list of sorted items visited so far. Initially an empty list is initialized as a sorted list. And we keep adding elements from the un-sorted list to the sorted list one by one.

For example, if we have an unsorted list [8, 2, 4, 1, 3], the algorithm performs the steps below to sort the list:

• Initially we have an input list which is assumed to be unsorted. An empty list is initialized as a sorted list with size same as that of the input list.

• The algorithm visits the first unvisited element in unsorted list (which is number 8), and adds it to the sorted list. As the sorted list we have so far is empty, we can insert number 8 at the first position and the list remains sorted.

• The algorithm visits the next unvisited element in the unsorted list (which is number 2) and adds It to the sorted list at correct position. Since we have number 8 already in the list which is greater than the number to insert (2), we move 8 to the right and then insert number 2.

• It then visits element 4, moves all elements greater than 4 in the sorted list by one place to the right, and inserts element 4 at the correct place.

• It then visits element 1, moves all elements greater than 1 in the sorted list by one place to the right, and inserts element 1 at the correct place.

• It then visits element 3, moves all elements greater than 3 in the sorted list by one place to the right, and inserts element 3 at the correct place.

That is it. We are finally left with the sorted list [1, 2, 3, 4, 8].

So the challenge in the algorithm boils to this: “Given a sorted list, how do we insert a new element to the list so that the list remains sorted?”. If we can do that, we can visit elements in unsorted list one by one and add it to the sorted list like we did previously.

And this is one of the optimum way to insert a new element to sorted list while maintaining the order:

• Find the position in the sorted list where the element to be added is. Let the position be P
• Move all the elements from this position P towards right by one position. This creates an empty space at position P
• Insert the element at position P and we end up with a sorted list!

For example, if the sorted list we have so far is [1, 2, 4, 8] and we need to add number 3 to the list while keeping the list sorted, we do the following:

• Move all numbers greater than 3 (the number to insert) towards right by one position
• The list becomes [1, 2, _, 4, 8]
• Insert the number (3) in the gap
• The list becomes [1, 2, 3, 4, 8]
• The list remains sorted!

In the actual algorithm, instead of maintaining two lists, we maintain the left portion of the input list always sorted and the algorithm slowly eats away the right unsorted portion and keeps building the left sorted portion of list. Go through the visualization below for better understanding.

Visualization of Insertion Sort Algorithm

Implementing Insertion Sort Algorithm

# Python program for Sorting an array using Insertion Sort

# Function that implements insertion sort
def insertionSort(arr):
  
  # Traverse through first element to the last element
  for i in range(len(arr)):
    
    # Store the current element in a variable "cnum"
    cnum = arr[i]
    
    # Move elements of arr[0..i-1], that are
    # greater than cnum, to one position ahead
    # of their current position
    j = i-1
    while j >=0 and cnum < arr[j] :
        arr[j+1] = arr[j]
        j -= 1
        
    # insert the current element in gap created
    arr[j+1] = cnum

# Let us now use the insertion sort algorithm
arr = [8, 2, 4, 1, 3]
insertionSort(arr)
print ("Sorted array is:")
for i in range(len(arr)):
  print ("%d" %arr[i])

// CPP program for Sorting an array using Insertion Sort

#include <iostream>

// Function that implements insertion sort
void insertionSort(vector<int> &array){
  // Traverse through each element in the array
  for(int i = 0; i < array.size(); i++){
    // Store the current element in a variable "cnum"
    int cnum = array[i];
    
    // Move elements of arr[0..i-1], that are
    // greater than cnum, to one position ahead
    // of their current position
    int insertPrevPos = i-1;
    while(insertPrevPos >= 0 && cnum < array[insertPrevPos]){
      array[insertPrevPos+1] = array[insertPrevPos];
      array[insertPrevPos]--;
    }
    
    // insert the current element in gap created
    // insertPrevPos is the position one less than gap position
    array[insertPrevPos+1] = cnum;
  }
}

// Let us now use the insetion sort algorithm
int main(){
  vector<int> arr = {8, 2, 4, 1, 3};
  insertionSort(arr)
  print ("Sorted array is: ")
  for(auto num : arr){
    std::cout << num << " ";
  }
}

Characteristics of Insertion Sort Algorithm

Time Complexity

In the best case scenario, all the elements given in the list might be already sorted and the algorithm just visits each element once. The total visits/operations will be proportional to the size of list and so the best case time complexity of the algorithm is O(n).

In the worst case scenario, where all the elements in the given list are in reverse order, for each iteration, the algorithm has to move all the elements visited so far to the right by one place. So the worst case time complexity of the algorithm is O(n^2).

Space Complexity

Since the sorting can be done “in place” without allocating any new array/list, the best and worst time complexities of the algorithm is O(1) i.e., constant space complexity.

Stability

Any sorting algorithm is said to be stable if the relative order of elements with similar id is maintained. For example, if we are given an unordered list of objects [1#, 2%, 1%, 2#], the output has to be [1#, 1%, 2%, 2#]. i.e., the relative order of similar elements has to be maintained.

In this algorithm, we move existing elements in the sorted portion of list only if it is greater than the number to insert. So we maintain relative order of similar elements and hence insertion sort is a stable algorithm.

Advantages

• The algorithm is relatively easy to implement
• The algorithm can take in and keep a list sorted as and when data is received
• This algorithm keeps the positions of elements with equal numbers in same relative positions. So this algorithm can be said to be a stable sort

Resources & References

• Wikipedia