// insert sort

public class insertsort {
    public static void main(String[] args) {
	print(insertsort(new int[] {4,2,1,3}));    }

    public static void print(int[] x) {
	System.out.println();
	for (int i=0; i<x.length; i++)
	    System.out.print(x[i] + " ");
    }

    public static int[] insertsort(int[] x) {

	// First element x[0] is sorted

	// Scan through remaining elements
	   for (int i=1; i<x.length; i++) {
	    
	    // Index $i$ gives current element $key$ to insert 
	    // in sorted portion:
	       int key=x[i]; // element to insert
	       int pos=i; // position of $key$ so far
	    
	    // Test $key$ with other elements.
	    // Each time, move the tested element to the right
	    // (causes a shift of sorted portion from left to right):
	       while(pos>0 && x[pos-1]>key) { 
		   x[pos]=x[pos-1];
		   pos--;
	       }

            // Insert $key$:
	       x[pos]=key;

	   }
	   
	   return x;

    }
    
}