JB Header
Insertion Sort in Java.
What is Insertion Sort Insertion sort works by progressively sorting a sub-list of the given list of items. With every iteration\pass the insertion sort algorithm keeps inserting the next item in the list in the correct position in this sorted sub-list.I.e. with every pass one item more is picked from the unsorted portion and is inserted in to the correct place in the sorted portion. YouTube video showing whiteboard animation video explanation of how insertion sort works and Java code walk-through
Insertion Sort's working explained Lets say the list which is to be sorted is [1000, 1, 100, 101, 15]. Now we will progressively build a sorted sub-portion of the list from the left of the list. We will call this left sorted sub-portion as sorted sub-list. And the other unsorted portion on the right of the list as unsorted sub-list.
Before we start with the insertion sort passes - the first item, 1000, is assumed to be sorted by virtue of being the only element and is deemed to be sorted in a single item list. Sorted sub-list thus has [1000] at this point. The insertion sort passes start with picking of the second element.

First pass of Insertion Sort
Before the pass: Sorted sub-list is [1000]  & Unsorted Sub-list is [1, 100, 101, 15]. 

The item at the head of the unsorted sub-list, i.e. 1, is picked to be placed in the sorted sub-list. Since 1 < 1000 it is placed before 1000 in the sorted sub-list. To make space for 1 the item 1000 is moved to the right by 1 place.

At the end of the pass: Sorted Sub-List is [1, 1000]  & Unsorted Sub-list is [100, 101, 15].

Second pass
At the start of second pass: Sorted Sub-List is [1, 1000]  & Unsorted Sub-list is [100, 101, 15] i.e same as the end of first pass.

We pick item at the head of unsorted sub-list,i.e 100, and place it at the correct place in the sorted sub-list. Since, 100 > 1 and 100 < 1000 so 1000 is moved 1 place to the right and 100 is placed before 1000.

At the end of the pass: Sorted sub-list is [1, 100, 1000]  & Unsorted Sub-list is [101, 15].

Remaining passes of the algorithm
In this way progressively every element from the head of the unsorted sub-list is picked up and inserted in its correct place in the sorted sub-list in exactly n-1 passes.
Lets look at the code for Insertion Sort in Java -
Insertion Sort Algorithm implemented in Java
package com.javabrahman.algorithms.sorts;
public class InsertionSort {
 static int intArray[] = { 1000, 1, 100, 101, 15 };
 public static void doSort() {
  for (int outer = 1; outer < intArray.length; outer++) {
   for(int inner=outer;inner > 0; inner--){
    if(intArray[inner] < intArray[inner-1]){
     int temp=intArray[inner];
     intArray[inner]=intArray[inner-1];
     intArray[inner-1]=temp;
     continue;
    }//if condition ends
   }//inner loop ends
  }//outer loop ends
 }
 public static void printArray() {
  for (int i = 0; i < intArray.length; i++) {
   System.out.print(" " + intArray[i]);
  }
 }
 
 public static void main(String args[]) {
  System.out.print("Array Before Sorting->");
  printArray();
  doSort();
  System.out.print("\nArray After Sorting ->");
  printArray();
 }
}

 OUTPUT of the above code
 Array Before Sorting-> 1000 1 100 101 15
 Array After Sorting -> 1 15 100 101 1000
Explanation of the insertion sort code
  • The doSort() method in the above java program holds the sorting logic.
  • There are 2 loops. The loop with the counter outer represents the passes and continues for 0 to length - 1 times. i.e. 1 less than the number of items times.
  • The loop with the counter inner represents the progressive picking of the head element from the unsorted sub-list. Note that the loop for inner iterates in reverse. It starts its iterations with the unsorted item and keeps on moving the items greater than this unsorted item to the right by progressively swapping the items greater than itself.While doing all this the inner loop keeps decrementing its counter in order to iterate in reverse.
  • The continue keyword in the inner loop prevents unnecessary iterations for inner loop once the correct place for the item being inserted is found.
  • The main() method orchestrates the sorting.
  • The instance element intArray[] holds the list to be sorted.