Insertion Sort Algorithm using Java

Insertion Sort is simple sort algorithm. In insertion sort, we pickup element and find correct place of element where it needs to be inserted and insert that element at correct place by moving elements to right side.We will keep doing same until we have all sorted elements available on left side.

Java Program using Insert Sort Algorithm :

package com.anuj.algorithms;

/**
 * 
 * @author Anuj
 *
 */
public class InsertionSort {

 public static void main(String[] args) {
  int a[] = { 12, 9, 4, 99, 120, 1, 3, 10 };
  insertionSort(a);
 }

 public static void insertionSort(int a[]) {

  for (int i = 1; i < a.length; i++) {
   int tmp = a[i];

   int j;
   for (j = i - 1; j >= 0 && tmp < a[j]; j--) {
    a[j + 1] = a[j];
   }
   a[j + 1] = tmp;
   printNumbers(a);
  }
 }

 private static void printNumbers(int[] input) {
  for (int i = 0; i < input.length; i++) {
   System.out.print(input[i]);
   if (i < input.length - 1) {
    System.out.print(",");
   }
  }
  System.out.println();
 }
}

Output:
9,12,4,99,120,1,3,10
4,9,12,99,120,1,3,10
4,9,12,99,120,1,3,10
4,9,12,99,120,1,3,10
1,4,9,12,99,120,3,10
1,3,4,9,12,99,120,10
1,3,4,9,10,12,99,120