procedure for Insertion sort:

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, or heapsort. However, insertion sort provides several advantages:

1. It is simple to implement

2. It is efficient for small data sets

3. It is efficient for data sets that are already nearly sorted.

4. Sorting can be done in place i.e. while reading the elements itself.

Insertion sort logic: Every iteration of insertion sort removes an element from the data, inserting it into the correct position in the already-sorted list. This process is repeated until no elements remain. The choice of which element to remove from the data is random.

Complexity: The time complexity of Insertion sort is shown below in three different cases and worst-case space complexity.

Worst Case	Best Case	Average Case	Worst case Space Complexity
O(n2)	O(n)	O(n2)	O(n) total, O(1) auxiliary

Example: The insertion sort starts with the first two elements and creates a sorted sub-list, which in the example contains 11 and 27. It then looks at the next element (1) and inserts it into the sub-list in its correct position (1, 11, 27). Then, It takes the next element (72) and does the same, continuing until the sub-list contains all the data.

Initial Data	27	→11	1	72	64	12
1st pass	11	27	→1	72	64	12
2nd pass	1	11	27	→72	64	12
3rd pass	1	11	27	72	→64	12
4th pass	1	11	27	64	72	→12
5th pass	1	11	12	27	64	72

Program: The following program uses bubble sort algorithm to sort the elements of the array

import java.io.*;

class InsSort

{

public static void main(String as[]) throws Exception

{

int i,j,n,t,a[]=new int[10];

InputStreamReader isr=new InputStreamReader(System.in);

BufferedReader br=new BufferedReader(isr);

System.out.println("How many values:");

n=Integer.parseInt(br.readLine());

System.out.println("Enter Values:");

for(i=0;i

a[i]=Integer.parseInt(br.readLine());

for(i=1;i

{

t=a[i];

for(j=i;j>0;j--)

{

if(a[j-1]>t)

a[j]=a[j-1];

else

break;

}

a[j]=t;

}

System.out.println("After Sorting");

for(i=0;i

System.out.print("\t"+a[i]);

}

}

Output:

How many values: 4

Enter Values:

45

36

87

12

After Sorting:

12 36 45 87