Insertion sort with program code and tutorial

Insertion sort is divided into two parts:

     1. Straight Insertion Sort

     2. Shell Sort 

Insertion sort is a simple sort algorithm, a comparison sort in which the sorted array [or list] is built one entry at a time. It is much less efficient on large lists than the more advanced  Algorithms such as Quick sort, Merge sort or Heap sort.

In abstract terms , in each iteration the sort  removes an element from the input data , inserting at the correct position in an array of  already sorted list, until no elements are left in the input.

Program Code :

public class Insertion {

    public void InSort(int a[],int n){
        int key=0;
        int j=0;
        for (int i=1;i<n;i++){
            key=a[i];
            j=i-1;
            while((j>=0) && (a[j]>key)){
                a[j+1]=a[j];
                j=j-1;
            }
            a[j+1]=key;
        }
        
        for(int i=0;i<n;i++){
            System.out.println(a[i]);    
        }
    }
    
    public static void main(String[] args) {
        new Insertion().InSort(new int[] {66,45,76,12,9,4},6);// Elements and number of elements
    }
}