Insertion Sort

Insertion sort is a simple sorting algorithm and it picks one item at a time, sort the elements finally produce the sorted array. Insertion sort is good for small size elements but not for large elements.
Insertion sort iterates though out the array and iterates are equal to array size. Each iteration, insertion sort removes one element from the input data and finds the location it belongs within the sorted list, and inserts it there. It repeats the same until end of the input array. Sorting typically done in place by comparing the each element and at every position and check there is any value largest against it. If larger element found it leaves the element in place and moves to the next and incase of smaller it finds the correct position within the sorted list, and place it there.
However, advantages of Insertion Sort are that it is efficient for (quite) small data sets, adaptive for data sets that are already substantially sorted, stable (i.e. does not change the relative order of elements with equal keys), In-place ( i.e. only requires a constant amount O(1) of additional memory space) and online (i.e. can sort a list as it receives it)

Worst Case Performance: O(n2) comparisons
Best Case Performance: O(n) comparisons
Average Case Performance: O(n2) comparisons
Worst Case space complexity: O(n) total and O(1) auxiliary

Algorithm for Insertion Sort:

// Sort an arr[] of size n
insertionSort(arr, n)
Loop from i = 1 to n-1.
……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1] Pseudo code for Insertion Sort:

for i ← 1 to length(A)
j ← i
while j > 0 and A[j-1] > A[j] swap A[j] and A[j-1] j ← j – 1
end while
end for

Let us see the below example for Insertion sort:

2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
0, 2, 4, 6, 9, 12, 23, 34, 1,
0, 1, 2, 4, 6, 9, 12, 23, 34,

Program for Insertion Sort in Java:

import java.util.Scanner;
public class InsertionSort
{
public static void sort( int arr[] )
{
int size = arr.length;
int i, j, temp;
for (i = 1; i< size; i++) { j = i; temp = arr[i]; while (j > 0 && temp < arr[j-1])
{
arr[j] = arr[j-1];
j = j-1;
}
arr[j] = temp;
}
}
public static void main(String[] args)
{
Scanner input = new Scanner( System.in );
System.out.println(“Insertion Sort over the given input n”);
int n, i;

/* Accept a number for sorting elements */
System.out.println(“Enter size of integer elements”);
n = input.nextInt();
/* Create integer array on n elements */
int arr[] = new int[ n ];
/* Accept elements */
System.out.println(“nEnter “+ n +” integer elements”);
for (i = 0; i < n; i++)
arr[i] = input.nextInt();
/* Call method sort */
sort(arr);
/* Print sorted Array */
System.out.println(“nElements after sorting “);
for (i = 0; i < n; i++)
System.out.print(arr[i]+” “);
System.out.println();
}
}

Output is :