Insertion.java

import java.util.Arrays;

/* Insert the next unsorted element into its correct position in the
   sorted portion by moving back all the values greter than it.

   Takes O(n^2) steps in the worse case, but could take fewer steps.
*/

public final class Insertion {
      
   // sort data[0]..data[n-1] into ascending order      
   public static void insertSort (int [] data) {
      final int n = data.length;

      for (int i=1; i<n; i++) {

         //  At this point data[0 .. i-1] is sorted.
         //  Now insert data[i] into its proper place in data[0..i]

         final int t = data[i];
         int j;

         //  The proper place for data[i] is an index j such that
         //      data[0..j-1] <= t < data[j..i-1]
         //  Find j and move elements data[j..i-1] to data[j+1..i].

         for (j = i; j>0 && t<data[j-1]; j--) {
            data[j] = data[j-1];
         }
         data [j] = t;
         if (verbose) System.out.printf ("%2d: %s%n", i, Arrays.toString(data));
      }
   }

   private static boolean verbose  = System.getProperty ("verbose")!=null;

   public static void main (String [] args) throws NumberFormatException {
      final int [] data  = new int [args.length];
      for (int i=0; i<data.length; i++) {
         data[i] = Integer.parseInt (args[i]);
      }

      System.out.printf ("..: %s%n", Arrays.toString(data));
      insertSort (data);
      System.out.printf ("**: %s%n", Arrays.toString(data));
   }
}