In this post, I would be discussing the implementation of insertion sort in Java programming language. Insertion sort is the sorting method which we humans usually use when sorting manually like sorting deck of playing cards. Insertion sort is a good method for partially sorted arrays. In this sorting method an element is removed from the array and is then inserted at its proper place.

Let us understand insertion sort with the help of an example:

6 5 3 1 8 7 2 4 
  ^
Second element to be compared with all previous element and 
inserted at its proper place

5 6 3 1 8 7 2 4 
    ^
Third element to be compared with all previous element and 
inserted at its proper place

3 5 6 1 8 7 2 4 
      ^
Fourth element to be compared with all previous element and 
inserted at its proper place

1 3 5 6 8 7 2 4 
        ^
Fifth element to be compared with all previous element and 
inserted at its proper place (no change)

1 3 5 6 8 7 2 4 
          ^
Sixth element to be compared with all previous element and 
inserted at its proper place

1 3 5 6 7 8 2 4 
            ^
Seventh element to be compared with all previous element and 
inserted at its proper place

1 2 3 5 6 7 8 4 
              ^
Eighth element to be compared with all previous element and 
inserted at its proper place

1 2 3 4 5 6 7 8

The Java implementation of insertion sort is as follows:

class InsertionSort{
    public static int[] insertionSort( int a[] ){
        int temp, x;
        for( int i=1 ; i < a.length; i++ ){
             temp = a[ i ];
             x = i - 1;
             while( x >= 0 && temp < a[x] ){
                a[ x + 1 ] = a[ x ];
                x--;
            }
            a[ x + 1 ] = temp;
        }
        return a;
    }
    public static void display( int a[] ){
        for( int n: a ){
            System.out.print( n + " " );
        }
        System.out.println( );
    }
    public static void main(String args[]){
        int a[]={8, 5, 2, 6, 9, 3, 1, 4, 0, 7};
        a = insertionSort( a );
        display( a );
    }
}

In the above Java program on insertion sort, the outer loop on line number 4, is for removing the element to be compared. The inner loop, on line number 7, is for comparing and shifting to make place for insertion of the element removed above.
As usual, the main function has purposely been kept to minimum and its expected that students will write appropriate input/output statements as per the requirement.