/**
 * Write a description of class InsertionSort here.
 *
 * @author (your name)
 * @version (a version number or a date)
 */
public class InsertionSort
{
    public static void insertionSort(int array[]){
        int n = array.length;
        for(int j=1; j<n; j++){
            int key = array[j];
            int i = j-1;
            while((i > -1) && (array[i] > key)){
                array[i+1] = array[i];
                i--;
            }
            array[i+1] = key;
        }
    }
    public static void main(String a[]){
        int[] arr1 = {9,14,3,2,43,11,58,22};
        System.out.println("Before Insertion Sort");
        for(int i:arr1){
            System.out.print(i+ " ");
        }
        System.out.println();

        //sorting array using insertion sort
        insertionSort(arr1);
        System.out.println("After Insertion Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
    }
}