Table of Contents

Insertion sort is a sorting algorithm in which the elements are transferred one at a time to the right position.

In other words, an insertion sort helps in building the final sorted list, one item at a time, with the movement of higher-ranked elements. It has the benefits of simplicity and low overhead.

The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst-case complexity are of Ο(n 2 ), where n is the number of items.

Insertion Sort Algorithm

insertionSort(array)
mark first element as sorted
for each unsorted element Xs
‘extract’ the element X
for j <- lastSortedIndex down to 0 if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort

Time Complexity Analysis:
Even though insertion sort is efficient, still, if we provide an already sorted array to the insertion sort algorithm, it will still execute the outer for loop, thereby requiring n steps to sort an already sorted array of n elements, which makes its best case time complexity a linear function of n. Wherein for an unsorted array, it takes for an element to compare with all the other elements which mean every n element compared with all other n elements. Thus, making it for n x n, i.e., n2 comparisons. One can also take a look at other sorting algorithms such as Merge sort, QuickSort, Selection Sort, etc. and understand their complexities.

Worst Case Time Complexity [ Big-O ]: O(n 2 )
Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n 2 )

How the Insertion Sort Algorithm works?

Let’s take an example:
Take an array A[] = [ 7, 5, 4, 2 ]

Since 7 is the first element has no other element to be compared with, it remains at its position. Now when on moving towards 4, 7 is the largest element in the sorted list and greater than 4. So, move 4 to its correct position i.e. before 7. Similarly with 5, as 7 (largest element in the sorted list) is greater than 5, we will move 5 to its correct position. Finally, for 2, all the elements on the left side of 2 (sorted list) are moved one position forward as all are greater than 2 and then 2 is placed in the first position. Finally, the given array will result in a sorted array.

Implementation of Insertion Sort Using C:

Following C program ask the user to enter array size and array element to sort the array using insertion sort technique, then display the sorted array on the screen:

// C program for insertion sort

include

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) { key = arr[i]; j = i – 1; while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j – 1;
}
arr[j + 1] = key;
}
}

// print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf(“%d “, arr[i]);
printf(“\n”);
}

/* program to test insertion sort */
int main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n); printArray(arr, n); return 0;

}

Implementation of Insertion Sort in C++:
Following C++ program ask the user to enter array size and array element to sort the array using insertion sort technique, then display the sorted array on the screen:

/* C++ Program – Insertion Sort */

#include<iostream.h>

#include<conio.h>
void main()
{
clrscr();
int size, arr[50], i, j, temp;
cout<<“Enter Array Size : “; cin>>size;
cout<<“Enter Array Elements : “; for(i=0; i>arr[i];
}
cout<<“Sorting array using selection sort … \n”; for(i=1; i=0))
{
arr[j+1]=arr[j];
j=j-1;
}
arr[j+1]=temp;
}
cout<<“Array after sorting : \n”;
for(i=0; i<size; i++)
{
cout<<arr[i]<<” “;
}
getch();
}

Implementation Through Java:

Following Java Program ask the user to enter array size and array element to sort the array using insertion sort technique, then display the sorted array on the screen:

/* Java Program Example – Insertion Sort */

import java.util.Scanner;

public class JavaProgram
{
public static void main(String args[])
{
int size, i, j, temp;
int arr[] = new int[50];
Scanner scan = new Scanner(System.in);

   System.out.print("Enter Array Size : ");
   size = scan.nextInt();

   System.out.print("Enter Array Elements : ");
   for(i=0; i<size; i++)
   {
       arr[i] = scan.nextInt();
   }

   System.out.print("Sorting Array using Insertion Sort Technique..\n");
   for(i=1; i<size; i++)
   {
       temp = arr[i];
       j = i - 1;
       while((temp < arr[j]) && (j >= 0))
       {
           arr[j+1] = arr[j];
           j = j - 1;
       }
       arr[j+1] = temp;
   }

   System.out.print("Array after Sorting is : \n");
   for(i=0; i<size; i++)
   {
       System.out.print(arr[i] + "  ");
   }

}
}

Implementation through Python:
Following Python program ask the user to enter array size and array element to sort the array using insertion sort technique, then display the sorted array on the screen:

# Python program for implementation of Insertion Sort

def insertionSort(arr):

# Traverse through 1 to len(arr) 
for i in range(1, len(arr)): 

    key = arr[i] 
      j = i-1
    while j >=0 and key < arr[j] : 
            arr[j+1] = arr[j] 
            j -= 1
    arr[j+1] = key

code to test above

arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print (“Sorted array is:”)
for i in range(len(arr)):
print (“%d” %arr[i]) ;
}

Relation With Other Sorting Algorithms:
Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. However, the fundamental difference between the two algorithms is that insertion sort scans backwards from the current key, while selection sort scans forwards. This results in selection sort making the first k elements the k smallest elements of the unsorted input, while in insertion sort they are simply the first k elements of the input.

The primary advantage of insertion sort over selection sort is that selection sort must always scan all remaining elements to find the absolute smallest element in the unsorted portion of the list, while insertion sort requires only a single comparison when the (k + 1)-st element is greater than the k-th element; when this is frequently true (such as if the input array is already sorted or partially sorted), insertion sort is distinctly more efficient compared to selection sort. On average (assuming the rank of the (k + 1)-st element rank is random), insertion sort will require comparing and shifting half of the previous k elements, meaning that insertion sort will perform about half as many comparisons as selection sort on average.

Difference between Selection, Bubble and Insertion Sort:

Algorithm: In Insertion sort, adjacent elements are compared and sorted if they are in the wrong order. We select the smallest element and swap it with the 0th index element in the first iteration. This selection continues for n-1 elements and a single element is already sorted. We will have an array sorted by 1 element in every iteration. Here, we create partitions of sorted and unsorted parts. One by one element from the sorted part is taken and sent to the unsorted part for checking and placing it to the right position in sorting using swaps.

Time & Space Complexity: All three sort have O(n2) time complexity. But via flag variable, we can reduce the time complexity of Insertion and insertion to O(n) is the best case. Space Complexity is the same for all i.e., O(1).

Speed: Insertion sort may work best with an already sorted array and there is no need for any extra flag.

In-Place: In-place states that the algorithm is in-place if it does not need extra memory barring some variable creation which counts to constant space. Selection and Insertion are in-place algorithms and do not require any auxiliary memory.

Stability: It states that the algorithm is stable if the relative ordering of the same elements in the input and output array remains the same. Insertion and Insertion are stable algorithms but naive selection is not as swapping may cost stability.

Conclusion: Insertion sort isn’t a particularly efficient algorithm but it is easy to understand and relatively straightforward to write up. There are a handful of different ways for implementing it and I encourage you to take the tests I provided and try to find a different way to implement it.

It is one of the easiest and brute force sorting algorithm.
Insertion sort is used to sort elements in either ascending or descending order.
In insertion sort, we maintain a sorted part and unsorted part.
It works just like playing cards.
With every iteration, one item is moved from the unsorted section to the sorted section.
The first element is picked and is considered sorted.
After this, we start picking from the second element onward and compare with elements in the sorted section.
We keep shifting the elements from the sorted section one by one until an appropriate location is found for that element.
This process is continued until all elements have been exhausted.

Want to read more about Data Structures & Algorithms, click here.

By Akhil Sharma