class SortTest
{
    static void insertionsort (int[] x)
    {
        for (int i=1; i < x.length; i++)
        {
            // insert x[i] into the already sorted
            // sequence  x[0]...x[i-1]
            int key = x[i];
            int j = i;
            while ( j > 0 && key < x[j-1] )
            {
                // key should be in front of x[j-1]
                x[j] = x[j-1];
                j-- ;
            }
            // now j==0  or, if j>0, then  x[j-1] <= key
            x[j] = key;
        }
    }

    public static void main (String[] args)
    {
        int[] A = {3, 5, 2, 1, 20};
        outarray(A, "before sorting:");
        insertionsort (A) ;
        outarray(A, "after sorting:");
    } 

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