Hi Readers,

This blog is to help you to understand how insertion sort works. Insertion sort is a simple sorting algorithm which is good to sort short list.

Real life example of insertion sort is sorting of playing cards, Like we pick a card and put it where it should come. Same process is repeated until all cards are in sorted order.

Insertion sort have simpler implementation and is efficient to sort small list of elements. Average case time complexity of Insertion sort is O(n*n).

In our below approach considering elements as cards we pick from second card to the last card in order.

As we picked the 2nd card it has to be matched to the previous card until picked card is greater than the previous one. Now that card will be placed after that element which had lesser value than the picked one. Now 3rd card will be picked and will be placed to its correct location. Cards has to be picked successively until we traversed the last card in hand.

Java Implementation for Insertion sort.

public class InsertionSortDemo {

	private static void insertionSort(int arr[]) {
		int len = arr.length;
		int temp;
		int j;
		for (int i = 1; i < len; i++) {
			if (arr[i] < arr[i - 1]) {
				// System.out.println("true");
				temp = arr[i];
				j = i;
				while (j > 0 && (temp < arr[j - 1])) {
					arr[j] = arr[j - 1];
					j--;
				}
				arr[j] = temp;
			}
		}
	}

	public static void main(String[] args) {
		int[] arr = { 10, 4, 2, 1, 325, 64, 57, 31, 2, 34, 5, 41, 674, 5, 83,
				47, 8, 5, 14, 3, 25, 8, 34, 756 };
		System.out.println("Before Sort");
		for (int i : arr)
			System.out.print(i + " ");
		System.out.println("\n");

		insertionSort(arr);
		System.out.println("After  Sort");
		for (int i : arr)
			System.out.print(i + " ");
		System.out.println();
	}
}

After running the above code output will be like this

Before Sort
10 4 2 1 325 64 57 31 2 34 5 41 674 5 83 47 8 5 14 3 25 8 34 756 

After  Sort
1 2 2 3 4 5 5 5 8 8 10 14 25 31 34 34 41 47 57 64 83 325 674 756 

Thanks for reading.