public class Insertion {

    public static int positionGE( int i, int [] data ) {
        int j = i;
        while( (j > 0) && (data[j - 1] > data[i]) ) {
            j = j - 1;
        } // while
        return j; 
    } // positionGE( int, int [] )

    public static void insert( int i, int j, int [] data ) {
        int temp = data[i];

        for( int k = i; k > j; k-- ) {
            data[k] = data[k - 1];
        } // for

        data[j] = temp;
    } // insert( int, int, int [] )

    public static void sort( int [] data ) {
        for( int i = 1; i < data.length; i++ ) {
            int j = positionGE( i, data );
            insert( i, j, data );
        } // for
    } // sort( int [] )

    public static void main( String [] args ) {

        int [] data = { 5, 2, 3, 1, 4 };
        sort( data );
        for( int i = 0; i < data.length; i++ ) {
            System.out.println( data[i] );
        } // for

    } // main( String [] )

} // Insertion