Insertion sort algorithm is a simple sorting algorithm that works the way we sort

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

Insertion sort is an

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.

**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.