Insertion sort algorithm

Insertion sort algorithm is a simple sorting algorithm that works the way we sort playing cards in our hands and builds the final sorted array one item at a time.

It is much less efficient on large data sets than more advanced algorithms such as quicksort, heapsort, or merge sort.

Insertion sort is an in-place, stable and online sorting algorithm that takes constant O(1) auxiliary space. Insertion sort is used when dataset (array) have a small number of elements where most of the elements are already sorted and only few elements are misplaced.

Insertion sort Time Complexity

Insertion sort takes maximum time О(n2), if elements are sorted in reverse order and it takes minimum time О(n) when elements are already sorted.

Worst case time complexity : О(n2) comparisons, swaps
Best case time complexity : O(n) comparisons, O(1) swaps
Average case time complexity : О(n2) comparisons, swaps

Insertion sort implementation in Java

Lets assume we have an array having (7, 2, 4, 6, 2, 5, 3, 1) integer elements, we will starts a loop from second element (i=1) to end of array (i=n), in each pass one element will get it's place in sorted array.

We will see if current element at index (i) is less than element at index (i-1), if so we will push elements to the left one place right until we reach the place to put current element.
``````
2, 7, 4, 6, 2, 5, 3, 1	i=1
2, 4, 7, 6, 2, 5, 3, 1	i=2
2, 4, 6, 7, 2, 5, 3, 1	i=3
2, 2, 4, 6, 7, 5, 3, 1 	i=4
2, 2, 4, 5, 6, 7, 3, 1	i=5
2, 2, 3, 4, 5, 6, 7, 1	i=6
1, 2, 2, 3, 4, 5, 6, 7	i=7
``````

```package com.tb.arrays.sort;

import java.util.Arrays;
import java.util.stream.Collectors;

public class InsertionSort {
static int[] input = { 7, 2, 4, 6, 2, 5, 3, 1 };

private static void sort(int[] input, int n) {

int i, j, tmp;
for (i = 1; i < n; i++) {
j = i;
tmp = input[i];
while (j > 0 && tmp < input[j - 1]) {
input[j] = input[j - 1];
j--;
}
input[j] = tmp;
}
}

private static String printArrays(int[] input) {
return Arrays.stream(input).mapToObj(String::valueOf).collect(Collectors.joining(", "));

}

public static void main(String[] args) {
System.out.println("Array before sort: " + printArrays(input));
sort(input, input.length);
System.out.println("Array after sort: " + printArrays(input));
}
}
```
Output: Output of above code will be something like this.

``````
Array before sort: 7, 2, 1, 6, 2, 5, 3, 4
Array after sort: 1, 2, 2, 3, 4, 5, 6, 7
``````
In this article we have seen "What is insertion sort?", insertion sort time complexity, usage and how to implement insertion sort in Java.