### Insertion Sort Algorithm - The Coding Shala

Last Updated: 20-Jan-2021
Home >> Algorithms >> Insertion Sort

In this post, we will learn what is Insertion Sort Algorithm and how it works. We will write a Java program for Insertion Sort.

## Insertion Sort Algorithm

Insertion sort is an algorithm to sort a given array. The Insertion sort works on the principle of inserting an element at a particular position, hence known as Insertion Sort.

#### Working of Insertion Sort Algorithm

The Insertion sort works as follows:
• step 1. We take an element as key starts from index 1.
• Step 2. we compare all previous elements from the key element index if elements are greater than the key we move them to the next index.
• Step 3. At last, we insert a key at the index where all the previous elements are less than or equals to the key.
Here is an example of the Insertion sort algorithm:
Array ->   17 25 31 13 2

key 25
17 25 31 13 2

key 31
17 25 31 13 2

key 13
17 25 31 31 2     -> 31 is bigger than key
17 25 25 31 2    -> 25 is bigger than key
17 17 25 31 2    -> 17 is bigger than key
insert key at index 0
13 17 25 31 2

key 2

final sorted array ->  2 13 17 25 31

#### Time Complexity of Insertion Sort

The time complexity of Insertion sort in the worst case is O(n^2). In the worst case, we have to compare all the n elements with all other n elements.

The time complexity of Insertion sort in Best Case is O(N). if we pass a sorted array still we need to check for all the n elements.

The time complexity of the Insertion sort in the Average case is O(N^2).

## Insertion Sort Algorithm Java Program

The following is the Java Program of Insertion Sort Algorithm:

```import java.util.Arrays;

//quick sort
//the coding shala

class Main{

public static void insertion_sort(int[] input) {
for(int i = 1;i<input.length; i++) {
int j = i-1;
int key = input[i];
while(j>=0 && input[j]>key) {
input[j+1] = input[j];
j--;
}
input[j+1] = key;
}
}

public static void main(String[] args) {
int[] input = {1,5,3,2,8,7,6,4};
int len = input.length;
insertion_sort(input);
for(int i=0;i<len;i++) {
System.out.print(input[i]+" ");
}
}
}
```

Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.