Insertion Sort is a simple sorting algorithm.It compares the current element with the largest value in the sorted array. If the current element is greater, then it leaves the element in its place and moves on to the next element else it finds its correct position in the sorted array and moves it to that position.

Worst case time complexity of insertion sort is O(n2).

Example:

Pseudocode of Insertion Sort Algorithm:

void insertionSort(int arr[], int n)
{
for (int i = 1; i < n; i++)
{
int key = arr[i];
int j = i-1;

/* check whether the adjacent element in left side is greater or
less than the current element. */

while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}



Another Example:

Input Elements: 11, 10, 12, 4, 5

• i = 1 iteration, insert 10 before 11 as it is smaller -> 10,11,12,4,5
• i=2 iteration, 12 will remain in the same position as all the elements before 12 are smaller than it.-> 10,11,12,4,5
• i=3 iteration, 4 will be moved to the beginning and all the elements 10 to 12 will move one position ahead from current position . -> 4,10,11,12,5
• i=4 iteration, 5 will be moved in to second postion from starting and elements 10 to 12 will move again one position ahead from the current position . -> 4,5,10,11,12

Implementation:

## C

#include <stdio.h>

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;
}
}

void showArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

int main()
{
int arr[] = { 6 , 7 , 3 , 5 , 2  };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
showArray(arr, n);

return 0;
}

## Java

class InsertionSort {

void sort(int arr[])
{
int n = arr.length;
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;

while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

static void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");

System.out.println();
}

public static void main(String args[])
{
int arr[] ={ 6 , 7 , 3 , 5 , 2  };

InsertionSort ob = new InsertionSort();
ob.sort(arr);

printArray(arr);
}
}



## Python

def insertionSort(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

arr = [6 , 7 , 3 , 5 , 2  ]
insertionSort(arr)
for i in range(len(arr)):
print (arr[i])


## C++

#include <bits/stdc++.h>
using namespace std;

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;
}
}

void showArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}

int main()
{
int arr[] ={ 6 , 7 , 3 , 5 , 2  };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
showArray(arr, n);

return 0;
}


Few Interview questions on Insertion Sort:

Question: What is the best, average and worst case time complexity of insertion sort?

• Worst Case: O(n^2) .
• Avegare Case: O(n^2)
• Best Case: O(n)

That’s all I have and thanks a lot for reading. Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance… 😉

Categories: Data Structure

$${}$$