// Sort ints using the InsertionSort algorithm.

public class InsertionSort
{
    public static void main(String[ ] argv)
    {
        int[ ] a = { 45, 76, 34, 23, 19, 54, 55 };
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println( );
        insertionSort(a);
        for(int i = 0; i < a.length; i++)
            System.out.print(a[i] + " ");
        System.out.println( );
    }

    public static void insertionSort(int[ ] a)
    {
        int i, j, temp;

        for(i = 1; i <= a.length - 1; i++)
        {
            // Save value of a[i] making room 
            // for next step.
            temp = a[i];

            // Shove elements up until correct insertion 
            // point is found for temp.
            for(j = i; j >= 1; j--)
                if (a[j - 1] > temp)
                    a[j] = a[j - 1];
                else
                    break;

            // Insert temp at correct location.
            a[j] = temp;
        }  
    }
}