Insertion Sort

    public int[] InsertionSort(int[] input)    {
        for(int i=1; i<input.length; i++)    {
            int val=input[i];
            int hole=i;
            while(hole>0 && val<input[hole-1])    {
                input[hole]=input[hole-1];
                hole--;
            }
            input[hole]=val;
        }
        return input;
    }