Insertion sort is a simple sorting algorithm, which consumes one input item for each repetition, and grow a sorted output list. In every iteration, removes one item from input data, find the exact location in the sorted list and inserts it there. This process will repeat as long as no input items remain.

Points to remember

• Data structure :  Array
• Worst-case performance : О(n2) comparisons and swaps
• Best-case performance : O(n) comparisons, O(1) swaps
• Average performance: О(n2) comparisons and swaps
• Worst-case space complexity : О(n) total, O(1) auxiliary

See Also: Data Structure and Algorithms Complexity (Big-O)

Advantage

• Simple Implementation and efficient for small data set.
• Not change relative order of elements which are already sorted
• Efficient in comparison to other Quadratic Sort (i.e O(n2)) like Bubble Sort or Selection Sort.
• Efficient for data set that are already sorted. Time Complexity( i.e O(n)).
• Only required constant amount of memory space , as size of data set. Space
  Complexity (i.e O(1))

Disadvantage

• Insertion sort is much less efficient on large lists in compare to algorithms such as quicksort, heapsort, or merge sort.

Insertion Sort Steps

Here * marks the value set on particular iteration.

2	6	3	8	4	1	5	0
2	6*	3	8	4	1	5	0
2	3*	6	8	4	1	5	0
2	3	6	8*	4	1	5	0
2	3	4*	6	8	1	5	0
1*	2	3	4	6	8	5	0
1	2	3	4	5*	6	8	0
0*	1	2	3	4	5	6	8

In following programs you will learn both the ways to implement Insertion Sort by For Loop and Recursion.

Insertion Sort with Loop

public class InsertionSort {
public static void main(String[] args) {
int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
System.out.println("Before Sorting :");
printArrayTR(items);

//Perform insertion sort
insertionSort(items);

System.out.println("After Sorting :");
printArray(items);
}

static void insertionSort(int items[])
{
int n = items.length;
for (int i = 1; i = 0 && items[j] > key) {
items[j + 1] = items[j];
j = j - 1;
}
items[j + 1] = key;
printArrayTR(items);
}

}
static void printArray(int items[])
{
for (int item:items)
{
System.out.print(item + " ");
}
System.out.println();
}
}

Output

Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8 

Insertion Sort with Recursion

public class InsertionSortRecursion {
public static void main(String[] args) {
int[] items = { 2, 6, 3, 8, 4, 1, 5, 0 };
System.out.println("Before Insertion Sorting :");
printArray(items);

//Perform insertion sort
insertionSort(items,items.length);

System.out.println("After Insertion Sorting :");
printArray(items);
}

static void insertionSort(int items[],int n)
{
//base case or termination condition
if(n= 0 && items[j] > last)
{
items[j+1] = items[j];
j--;
}
items[j+1] = last;
}

static void printArray(int items[])
{
for (int item:items)
{
System.out.print(item + " ");
}
System.out.println();
}
}

Output

Before Insertion Sorting :
2 6 3 8 4 1 5 0 
After Insertion Sorting :
0 1 2 3 4 5 6 8