Insertion Code Recursive:

insertion Sort(datatype A[], int n)
{ // Input array is A[0:n-1]
if (n <= 1)
return;
insertion Sort( A, n-1 );
last = A[n-1];
j = n-2;
while (j >= 0 && arr[j] > last)
{
A[j+1] = A[j];
j--;
}
A[j+1] = last;
}

Program

1. public class InsertionSortExample {  
2.     public static void insertionSort(int array[]) {  
3.         int n = array.length;  
4.         for (int j = 1; j < n; j++) {  
5.             int key = array[j];  
6.             int i = j-1;  
7.             while ( (i > -1) && ( array [i] > key ) ) {  
8.                 array [i+1] = array [i];  
9.                 i--;  
10.             }  
11.             array[i+1] = key;  
12.         }  
13.     }  
14.        
15.     public static void main(String a[]){    
16.         int[] arr1 = {9,14,3,2,43,11,58,22};    
17.         System.out.println(\"Before Insertion Sort\");    
18.         for(int i:arr1){    
19.             System.out.print(i+\" \");    
20.         }    
21.         System.out.println();    
22.             
23.         insertionSort(arr1);//sorting array using insertion sort    
24.            
25.         System.out.println(\"After Insertion Sort\");    
26.         for(int i:arr1){    
27.             System.out.print(i+\" \");    
28.         }    
29.     }    
30. }