In this article, we will be **discussing Insertion sort in C, C++, Java with examples, complete algorithm, and time complexity calculation**.

Prerequisites:Bubble Sort, Selection Sort

**What is Insertion Sort Algorithm?**

Insertion sort is slightly different from the other sorting algorithms. It is based on the idea that each element in the array is consumed in each iteration to find its right position in the sorted array such that the entire array is sorted at the end of all the iterations.

In other words, **it compares the current element with the elements on the left-hand side (sorted array)**. If the current element is greater than all the elements on its left hand side, then it leaves the element in its place and moves on to the next element. Else it finds its correct position and moves it to that position by shifting all the elements, which are larger than the current element, in the sorted array to one position ahead.

Conclusion: Each iteration of insertion sort causes the sorted subset to grow, and the unsorted subset to shrink.

**Insertion Sort Example & Working**

Let us consider an array with 5 elements, A = [7, 1, 23, 4, 19]. **Below is how insertion sort works for this array**.

**Insertion Sort Pseudo Code**

Here is the pseudocode implementation of Insertion sort.

for i = 1 to n

key = arr[i]

j = i - 1

// comparing whether the first element is greater than the second element

// if yes, then store the largest element to the next position

while j >= 0 and arr[j] > key

arr[j + 1] = arr[j]

j = j - 1

end while

// storing the smallest element in the correct position

arr[j + 1] = key

end for

**Insertion Sort in C, C++, Java**

We will now look into implementing insertion sort in C, C++, Java languages. In case you guys have solutions in other languages, then make sure you post it in the comments section of this article to help your friends.

#include<stdio.h>

int main()

{

int i, n, j, temp, min, key;

scanf("%d", &n);

int arr[n];

for(i = 0; i < n; i++)

{

scanf("%d", &arr[i]);

}

for (i = 1; i < n; i++)

{

key = arr[i];

j = i - 1;

// comparing whether the first element is greater than the second element

// if yes, then store the largest element to the next position

while (j >= 0 && arr[j] > key)

{

arr[j + 1] = arr[j];

j = j - 1;

}

// storing the smallest element in the correct position

arr[j + 1] = key;

}

for(i = 0; i < n; i++)

{

printf("%d ", arr[i]);

}

}

#include<iostream>

using namespace std;

int main()

{

int i, n, j, temp, min, key;

cin >> n;

int arr[n];

for(i = 0; i < n; i++)

{

cin >> arr[i];

}

for (i = 1; i < n; i++)

{

key = arr[i];

j = i - 1;

// comparing whether the first element is greater than the second element

// if yes, then store the largest element to the next position

while (j >= 0 && arr[j] > key)

{

arr[j + 1] = arr[j];

j = j - 1;

}

// storing the smallest element in the correct position

arr[j + 1] = key;

}

for(i = 0; i < n; i++)

{

cout << arr[i] << " ";

}

}

import java.util.Scanner;

public class Main

{

public static void main(String args[])

{

Scanner sc = new Scanner(System.in);

int i, j, temp, min, key;

int n = sc.nextInt();

int arr[] = new int[n];

for(i = 0; i < n; i++)

{

arr[i] = sc.nextInt();

}

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;

}

for(i = 0; i < n; i++)

{

System.out.print(arr[i] + " ");

}

}

}

**Input:**

5

12 3 4 9 6

**Output:**

3 4 6 9 12

**Insertion Sort Time Complexity**

Similar to Bubble sort and Selection sort, the **time complexity of Insertion sort is also O(n²). **This is because, in the worst case, i.e when the given array is in the exact reverse order as that of the output, each element has to be compared with all the n elements in the sorted array. So this makes it n*n.

- Best case time-complexity:
**O(n). This occurs when the given array is already sorted.** - Worst case time complexity:
**O(n)** - Space Complexity:
**O(1)**