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.

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.

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

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

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

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

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

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

Key: 5

It will start searching from 2^nd 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.

After 2^nd pass 3 elements will be sorted.

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

Key: 2

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

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

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

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

After 3^rd pass 4 elements will be sorted.

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

Key: 3

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

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

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

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

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

After 4^th pass 5 elements will be sorted.

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

Key: 6

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

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

We will insert our key in the next index.

After 5^th pass 6 elements will be sorted.

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

Key: 7

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

6^th 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.

After 6^th pass 7 elements will be sorted.

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.