### 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

follow same steps

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**

- Counting Sort Algorithm
- Bucket Sort Algorithm
- Bubble Sort Algorithm
- Binary Search Algorithm
- The Big O Notation

## Comments

## Post a Comment