public class InsertionSort {

    static int cnt = 0;
    static int max = 0;
    static int N = 20;
    static double a[] = new double[N];
    static double h[] = new double[N];

    static void insert(double x){
        // find the right position, p
        int p = max+1;		// in case x is larger than any h[]
        for(int i = 0; i <= max; i++){
            cnt++;
            if(x < h[i]){
                p = i;
                break;
            }
        }
        // make room at p, move h[p]..h[max] to right
        for(int j = max; j >= p; j--)
            h[j+1] = h[j];
        h[p] = x;
        max++;
    }

    static void insertion(double [] a, int l, int r){
        for(int i = l; i <= r; i++){
            insert(a[i]);
        }
    }

    public static void main (String[] args){
        for(int i = 0; i < N; i++)
            a[i] = Math.random();
        h[0] = a[0];
        insertion(a, 1, N-1);
        if( N < 100 )
            for(int i = 0; i < N; i++)
                System.out.println(h[i] + " ");
        System.out.println("Compares used: " + cnt);
    }
}