### How to implement Insertion Sort in java

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or mergesort. However there are some advantages of insertion sort.

- It is very efficient for small data sets.
- It does not change the relative order of elements with equal keys.
- Requires a constant amount O(1) of additional memory space.

#### Performance of Insertion Sort.

Worst case performance : О(n2) comparisons

Best case performance : O(n) comparisons

Average case performance : О(n2) comparisons

#### Understand Insertion sort with an example.

**1st index iteration:** Value at position 1 is 5 which is less than value at position 0, So after iteration 1 array becomes [10, 5, 87, 32, 14, 22].

**2nd index iteration:** Value at position 2 is 87 which is greater than 10, so array remains same after 2nd iteration which is [10, 5, 87, 32, 14, 22].

**3rd index iteration:** Value at position 3 is 32 which is less than 87, So after iteration 3 array becomes [5, 10, 32, 87, 14, 22].

**4th index iteration**: Value at position 4 is 14 which is less than 87, so array becomes [5, 10, 32, 14, 87, 22]. Again 14 is less than 32, so array becomes [5, 10, 14, 32, 87, 22]. This time 14 is greater than 10 so after iteration 4 array becomes [5, 10, 14, 32, 87, 22].

**5th index iteration**: Value at position 5 is 22 which is less than 87, so array becomes [5, 10, 14, 32, 22, 87]. Again 22 is less than 32, so array becomes [5, 10, 14, 22, 32, 87]. This time 22 is greater than 14 so after iteration 5 array becomes [5, 10, 14, 22, 32, 87].

#### Let us see how this can be implemented in Java.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
package com.code2succeed.sorting; import java.util.Arrays; public class InsertionSortExample { public static void main(String[] args) { int [] a = {10, 5, 87, 32, 14, 22}; System.out.println("Array Before Sorting : "); print(a); insertionSort(a); System.out.println("Array After Sorting : "); print(a); } public static void insertionSort(int [] a){ int temp; int length = a.length; for(int i=1; i<length; i++) { for(int j=i; j>0; j--) { if(a[j] < a[j-1]) { temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } } System.out.println("Array after iteration "+i); print(a); } } public static void print(int [] a) { System.out.println(Arrays.toString(a)); } } |

#### Output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Array Before Sorting : [10, 5, 87, 32, 14, 22] Array after iteration 1 [5, 10, 87, 32, 14, 22] Array after iteration 2 [5, 10, 87, 32, 14, 22] Array after iteration 3 [5, 10, 32, 87, 14, 22] Array after iteration 4 [5, 10, 14, 32, 87, 22] Array after iteration 5 [5, 10, 14, 22, 32, 87] Array After Sorting : [5, 10, 14, 22, 32, 87] |