# 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 0th index. If elements of input are greater than key then they will be shifted to one index greater. But we reached 0th index so we will replace 0th 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 3rd element as key which is at index 2.

Key: 5 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. After 2nd pass 3 elements will be sorted. Step 3: In pass 3, key element will be 4th element that means index 3.

Key: 2 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. 1st element is 1, it is lesser than key so it will stop shifting and it will insert in the 2nd position. After 3rd pass 4 elements will be sorted. Step 4: In 4th pass key element will be 4th element.

Key: 3 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. Insert the key into the index next to the 2nd element. After 4th pass 5 elements will be sorted. 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. After 5th pass 6 elements will be sorted. 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. After 6th 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.

Output

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