// InsertionSort
import java.io.*;

public class InsertionSort 
{
    private int [] a;
               
    // make a private copy of the array
    private void copyArray(int [] data)
    {
        a = new int[data.length];
        
        for ( int i = 0; i < data.length; i++ )
        {
            a[i] = data[i];
        }
    }
    
    // copies data into array a and sorts with Insertion Sort
    public void sort( int [] data )
    {
        int j, save;
        
        if ( data == null ) return;
        
        int min, temp;
        
        copyArray( data );
        
        // Insertion Sort
        for ( int i = 1; i < a.length; i++ )
        {
            save = a[i];
            j = i - 1;
            while ( j >= 0 && a[j] > save )
            {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = save;
        }
    }
    
    // return a new copy of the array
    public int[] getSorted()
    {
        int [] ret = new int[a.length];
        
        for ( int i = 0; i < ret.length; i++ )
        {
            ret[i] = a[i];
        }
        
        return ret;
    }

}