First we understand what is insertion sort,Insertion sort is a simple sorting algorithm that builds the final sorted list(or array) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

It always maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger.

now,Lets implement insertion sort in java.

public class MyInsertionSort { public static void main(String[] args) { int[] input = {4,2,6,7,1,0,9,8,5,3}; insertionSort(input); } private static void printNumbers(int[] input) { for (int i = 0; i < input.length; i++) { System.out.print(input[i] + ", "); } System.out.println("\n"); } public static void insertionSort(int array[]) { int n = array.length; for (int j = 1; j < n; j++) { int key = array[j]; int i = j-1; while ( (i > -1) && ( array [i] > key ) ) { array [i+1] = array [i]; i--; } array[i+1] = key; printNumbers(array); } } }OUTPUT: