In java we have different sorting algorithm for insertion of element in an array. Let's talk about insertion sort today insertion sort is a uncomplicated algorithm, it raise the ultimate sorted array one item at a time. It is less coherent on huge list than other sorting algorithms.

Benefits of insertion sort

1. It is very uncomplicated algorithm.
2. It is very methodical for small data sets.
3. It is very fixed; i.e. it does not change the order of elements with equal keys.

Insertion sort repeat through the list by ingesting one element at each iteration, and building a sorted output list. On each iteration, insertion sort discard one element from input data, search the location it belongs with the sorted list and append it there. It keeps on repeating until no element is left.

The best case input in an array is an already sorted array. In that case the running time of each iteration is O(n). The first element is compared with the rightmost  section of already subsorted array. Worst case is to sort the array in the reverse order the complexity is O(n2). Average case makes it impracticle for large arrays. Insertion sort is basically used for sorting very small arrays.

Lets look at an example:

1. Compare first element is compared with the second,as second  is less than first. Then we have reached to 0th index, we will place second element to 0th index.

2. Compare third with second. Now compare third with with first and so on until we get the finally sorted array.

public class InsertionSortMain {  
   
   
 public static void main(String args[])  
 {  
  int  arr[]={110,30,25,40,10,85};  
  insertionSort(arr);  
   
 }  
    
 public static int[] insertionSort(int arr[])  
 {  
  for (int i = 1; i < arr.length; i++) {  
   int valueToSort = arr[i];  
   int j;  
   // If we get smaller value than valueToSort then , we stop at that index.  
     
   for ( j = i; j > 0 && arr[j - 1] > valueToSort; j--) {  
     arr[j] = arr[j - 1];  
   }  
            
   // We will put valueToSort at that index  
                        arr[j] = valueToSort;  
                        System.out.print("Iteration "+(i)+": ");  
   printArray(arr);  
  }  
    
  return arr;  
 }  
   
 public static void printArray(int arr[])  
 {  
  for (int i = 0; i <arr.length; i++) {  
   System.out.print(arr[i]+" ");  
  }  
  System.out.println();  
 }  
}  

Output for the above code is:

Iteration 1: 30 110 25 40 10 85   
Iteration 2: 25 30 110 40 10 85   
Iteration 3: 25 30 40 110 10 85   
Iteration 4: 10 25 30 40 110 85   
Iteration 5: 10 25 30 40 85 110