The Insertion sort is a very simple algorithm. It is a Sorting Algorithm. Insertion sort is used for sorting the linear data structures such as Linked List, Array etc.

It is very similar to Bubble Sort algorithm. Insertion Sort technique is very similar to as a human will manually sort any linear data such as playing cards etc.

Insertion sort is built around the technique of inserting elements one by one in the sorting list.

Let’s understand it with Examples :

Introduction

In Insertion Sort Java, In the very Beginning of Sorting we assume that the very first element is already sorted.

In next step, We pick the next element i.e the element at 1st index (in array, as array starts from 0th index),

We compare this element with the first element and if the element is lesser than the first element then we swap these two elements.

This brings us a new sorted list of only 2 elements.

Next, We pick the third element and compare this element with the second element. Again, Compare them and swap them if not in sorting order.

Now , If the present three elements are not in sorted order then we do the swapping process again for the 1st and 2nd element.

This brings us a new sorted list of only 3 elements.

This process is repeated until all the elements are not sorted.

In Best case, Only one comparison and none swapping is required.

In Worst case, We require n comparisons and n-1 swapping. Where n is the length of list.

The idea of insertion sort is very similar to real life sorting experience. For Example : Its process is very similar to how you play cards and sort them manually.

Pseudo Code for Insertion sort Java

In the Insertion Sort algorithm, We need to assume that the first element is sorted. So we will start the loop from the second element and not from first element.

In below pseudo code , we are using array. As array index is started from zero that’s why we are starting the loop from the first index.

n represents the length of array (the number of elements in array).

// Below is the outer loop 
// This is to iterate from each elements
// Starting from 1 as we are assuming first elements is sorted

for x=1 to n-1 { 
int current = A[x]; y = x ; 


// Performing insertion
// And comparison 

while(y> 0) and A[y-1] > current
{ 

swapping(A[y-1], A[y]); y = y -1; 

} 

}

Insertion sort Algorithm

Below is the Insertion Sort Algorithm explained in very easy and simple steps :

• There are two section of Elements – Sorted and Unsorted Section.

• Firstly, Take one element from the unsorted section. (Do not take the first element as we assume the first element is already sorted.)

• Then, Insert that element in the sorted section of elements. The element needs to be inserted on the basis of comparable property at the right position.

• Now, Repeat the above two steps until the unsorted section of elements does not become empty.

Insertion Sort Algorithm Example

Suppose, we need to perform insertion sort algorithm into the below unsorted array :

 [6, 5, 15, 3, 9]

Now , Below will be our steps to perform insert sort in this array :

1st index iteration

• The value at 1st index is 5
• As this value is lesser than the value 6 so the array will now be [6, 6, 15, 3, 9]
• We have reached at the 0th index so the array will now be [5, 6, 15, 3, 9]

2nd index iteration

• The value at 2nd index is 15
• And that is greater than the value 6 so now the array will be [5, 6, 15, 3, 9]

3rd index iteration

• The value at 3rd index is 3
• And that is lesser than 15 so now array will be [5, 6, 15, 15, 9]
• Now the value 3 is lesser than 6 so array will now be [5, 6, 6, 15, 9]
• Now the value 3 is lesser than 5 so now array will be [5, 5, 6, 15, 9]
• We have reached to the 0th index so array will now be [3, 5, 6, 15, 9]

4th index iteration

• The value at 4th index is 9
• Array will now be [3, 5, 6, 15, 15]
• Now 8 is greater than the value 5 so array will now be [3, 5, 6, 9, 15]

Array is now sorted.

Input : [6, 5, 15, 3, 9]

Output : [3, 5, 6, 9, 15]

Insertion Sort Java Implementation

Below is the illustrative example of Insertion Sort Java implementation :

This is sorting an array of integers.

Input : [6, 15, 5, 23, 19]

Output : [5, 6, 15, 19, 23]

public class InsertionSortJavaImpl {  

    public static void insertionsort(int arr[]) {  

        int len = arr.length;  

        for (int i = 1; i < len; i++) {  

            int temp = array[i];  
            int j = i-1;  
            while ( (j > -1) && ( arr [j] > temp ) ) {  
                arr [j+1] = array [j];  
                j--;  
            }  
            array[j+1] = temp;  
        }  
    }  
       
    public static void main(String a[]){    

        int[] arrayInt = {6, 15, 5, 23, 19}; 
   
        System.out.println("Before Sorting");   
 
        for(int i:arrayInt){    
            System.out.print(i+" ");    
        }    
        System.out.println();    
            
        insertionsort(arrayInt); 
           
        System.out.println("After Sorting using Insertion Sort");    
        for(int i:arrayInt){    
            System.out.print(i+" ");    
        }    
    }    
}    

Output:

 [5, 6, 15, 19, 23]  

Insertion Sort Performance Improvement

The above version of Insertion Sort Java implementation is not improved for performance.

In that java implementation for insertion sort, it takes a huge amount of time to find the correct position in the already sorted array (the sorted section of elements). We can improve this parameter by using some algorithm which performs more fast search.

The Binary Search Algorithm is very efficient for the already sorted arrays. So we can use it in our program to make it more efficient.

Let’s look at the improved Java implementation of Insertion Sort Algorithm :

Input : [6, 15, 5, 23, 19]

Output : [5, 6, 15, 19, 23]

public class InsertionSortJavaImpl 
{
    public static void main(String[] args) 
    {
  
        Integer[] arr = new Integer[] { 6, 15, 5, 23, 19 };
 
      
        sort(arr, 0, arr.length);
        
        System.out.println(Arrays.toString(arr));
    }
 
    @SuppressWarnings({ "rawtypes", "unchecked" })
    public static void insertionSortImproved(Object[] array, int from, int to) 
    {
        Object obj;
        for (int i = from + 1; i < to; i++)
        {
            obj = array[i];
            int left = from;
            int right = i - 1;

            if (((Comparable) array[right]).compareTo(obj) > 0) 
            {
                //Performing the binary search
                while (right - left >= 2) 
                {
                    int middle = (right- left) / 2 + left - 1;

                    if (((Comparable) array[middle]).compareTo(obj) > 0) {
                        right = middle ;

                    } else {
                        left = middle + 1;
                    }
                }
                if (right - left == 1) 
                {
                    int middle = left ;
                    if (((Comparable) array[middle]).compareTo(obj) > 0) {
                        right = middle ;
                    } else {
                        left = middle + 1;
                    }
                }
                //Placing the element

                int j = i;
                for (j = i; j > left ; j--) 
                {
                    array[j] = a[j - 1];
                }
                array[j] = obj;
            }
        }
    }
}
 

Output:

  [5, 6, 15, 19, 23]   

This has more line of codes but it is improved in terms of performance.

Insertion Sort Complexity

Insertion Sort is considered as efficient but still as i said earlier, if a sorted array is provided as input in insertion sort algorithm then it is still going to execute the first loop (outer).

Hence, the array is already sorted still this algorithm will perform n steps to sort it.

So if the array is of n elements then the best case time complexity will be high as n.

If the array is unsorted then every element will be compared with every element.

It means n elements will be compared to n elements.

So the comparison will be very high as n x n.

Worst Case Complexity

O(n2)

Let’s suppose, we have an array which is in ascending order and the requirement is to sort it in descending order.

This is the example of worst case complexity.

Every element needs to be compared with each and every other element.

So for the every nth element , there will be (n – 1) comparisons.

It means , we will have total number of comparisons as = n*(n-1) ~ n2

Best Case Complexity

O(n)

In the scenario, where array is already sorted it is called as Best Case complexity.

It will only require the outer loop to be executed so it will execute n number of times.

Thus the comparison will be equal to n.

Average Case Complexity

O(n²)

This is the case , where elements are neither is ascending nor descending order.

Space Complexity

As we have seen in above example, we were using an extra variable temp thus Space complexity is O(1) .

Insertion sort Advantages

As we know that Insertion Sort is a very simple algorithm like Bubble Sort But it is definitely slower than the other complex sorting algorithms like Merge Sort.

But Insertion Sort has many advantages over other complex algorithms. Let’s look at them :

• Insertion Sort is a very adaptive algorithm. It is very efficient for the elements which are nearly already substantially sorted.

• It is very efficient for smaller data input sets.

• Insertion Sort technique is very stable in compare to others. It never changes the elements’ relative orders with their equal keys.

• This algorithm is online which means it can sort a list as it receives it.

Some Important Points to Remember

Time Complexity	O(n*2)
Algorithmic Paradigm	Incremental Approach
Auxiliary Space	O(1)
Stable	Yes
Sorting In Place	Yes
Online	Yes

Conclusion

Insertion Sort is very simple algorithm for sorting in Java. It works best with lesser elements.

We have learned its all the details, algorithm, pseudo code, Java implementation, Its complexities, Its advantages etc with examples.