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 } }