Insertion Sort in Java

In this tutorial you will learn about insertion sort in Java with example and program.

Insertion Sort Principle

The strategy behind this sorting is much similar to playing cards. In cards playing we used to see that player will hold the cards in sorted manner. Whenever he wants to insert a new card he will put that in such way that again the cards in hand should be in sorted manner only. The below image can illustrate the phenomenon. When he is inserting the card number ‘7’, He is searching for correct position to put it in remaining cards.

Insertion Sort Principle (Playing Cards)

Image Source

Insertion Sort Example

Now we will see insertion sort with one numerical example.

Let us take one array which is having 7 elements for easy understanding. Now we want to sort this array in ascending order. And assume array index is from 0.

Insertion Sort 1

Step 1: It will start from second element because first element is only one and it is already sorted. Now consider second element which is at index 1 as key in first pass.

Key: 1

Insertion Sort 2

It will start searching from previous index of key to downwards until 0th index.

Insertion Sort 3

If elements of input are greater than key then they will be shifted to one index greater.

Insertion Sort 4

But we reached 0th index so we will replace 0th index with our key element.

Insertion Sort 5

After completing first pass, two elements will be sorted in our array form left to right.

Insertion Sort 6

Step 2: It will take 3rd element as key which is at index 2.

Key: 5

Insertion Sort 6

It will start searching from 2nd element means index 1 to downwards.

Second element is ‘4’ which is less than that key. We already know that it is sorted sub array. So we need not shift the element. We can put our key in its place only.

Insertion Sort 8

After 2nd pass 3 elements will be sorted.

Insertion Sort 9

Step 3: In pass 3, key element will be 4th element that means index 3.

Key: 2

Insertion Sort 10

Now it will start searching from 3rd element that means index 2 to downwards.

3rd element is 5, it is greater than key so it will shift it to one index greater.

2nd element is 4, it is greater than key so it will shift it to one index greater.

Insertion Sort 11

1st element is 1, it is lesser than key so it will stop shifting and it will insert in the 2nd position.

Insertion Sort 12

After 3rd pass 4 elements will be sorted.

Insertion Sort 13

Step 4: In 4th pass key element will be 4th element.

Key: 3

Insertion Sort 14

It will start searching from 4th element  that means 3rd index to downwards.

4th element is ‘5’, it is greater than key so it will be shifted to one index greater.

3rd element is ‘4’, it is greater than key so it will be shifted to one index greater.

2nd element is ‘2’, it is lesser than key so we will stop shifting.

Insertion Sort 15

Insert the key into the index next to the 2nd element.

Insertion Sort 16

After 4th pass 5 elements will be sorted.

Insertion Sort 17

Step 5: In 5th pass key is 6th element that means 5th index .

Key: 6

Now we start searching from 5th element means 4th index to downwards.

5th element is 5 which is less than the key so we will stop shifting.

We will insert our key in the next index.

Insertion Sort 18

After 5th pass 6 elements will be sorted.

Insertion Sort 19

Step 6: In 6th pass, 7th element means which is at index ‘6’ will be key.

Key: 7

It will start searching from 6th element means from index ‘5’ to downwards.

6th element is 6 which is less than the key so we will stop shifting.

We will insert our key in the next index to the index where we stopped shifting.

Insertion Sort 20

After 6th pass 7 elements will be sorted.

Insertion Sort 21

If total input size is ‘N’ then it will be sorted in ‘N-1’ passes.

Complexity of Insertion Sort Algorithm

It is taking N-1 steps to solve entire array.

In each step it is checking for correct place to insert the key element by comparing. In worst case it is comparing with N-1 elements.

So total time complexity is (N-1)*(N-1) which will give us O(N^2) worst case time complexity.

But in best case means if array is already sorted then it won’t check entire array to place the key. So in best case it is Ω(N).

Now we will see program for insertion sort.

Program for Insertion Sort in Java

public class InsertionSort
{
	public void insertionSort(int[] arr)
	{
		int i,j,n=arr.length;
		int key;
		
		//this code is for finding correct place to insert key
		for(i=1;i<n;i++)
		{
			key=arr[i];
			
			//it will start searching from previous index to the index of the key
			j=i-1;
			
			//search will be continued until just small element than key is found
			while(j>=0 && key<arr[j])
			{
				arr[j+1]=arr[j];
				j=j-1;
			}
			
			//after finding small element we will insert our key in the next index.
			arr[j+1]=key;
		}
	}
	
	public static void main(String args[])
	{
		int a[]={4,1,5,2,3,6,7},i;
		int n=a.length;
		InsertionSort obj=new InsertionSort();
		
		System.out.print("before sorting\n");		
		for (i=0;i<n;i++)
		{
			System.out.print(a[i]+" ");
		}
		
		//here we are calling insertion sort on our input array.
		obj.insertionSort(a);
		
		//now our input is sorted using insertion sort
		System.out.print("\nafter sorting\n");
		for (i=0;i<n;i++)
		{
			System.out.print(a[i]+" ");
		}
	}
}

Output

before sorting
4 1 5 2 3 6 7
after sorting
1 2 3 4 5 6 7

Advantages

  • Suits well for smaller inputs. Even asymptotically faster algorithms like merge sort, quick sort also using insertion sort when threshold (reached some small size) is reached to improve performance. Because they have recursion overhead.
  • If input is already sorted then it will exhibit best running time.
  • It is in place algorithm space efficient.
  • Stable algorithm.

 Comment below if you have any queries regarding above tutorial for insertion sort in Java.

Leave a Comment

Your email address will not be published. Required fields are marked *