InsertionSort.java

import java.util.Arrays;

/**
 * Insertion sort algorithm.
 * Illustrates the execution of the algorithm on the array
 * Integer[] array = {2, 11, 98, 23, 48, 33, 97, 61, 3},
 * writing the intermediate values of n at each iteration of the algorithm.
 */
public class InsertionSort {

    /**
     * Sorts an array of comparable objects into ascending order using the insertion sort algorithm.
     *
     * @param array An array of Comparable objects.
     */
    public static <T extends Comparable<? super T>> void insertionSort(T[] array) {
        int count = 1;
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            T element = array[i];
            while (j >= 0 && element.compareTo(array[j]) < 0) {
                System.out.printf("Iteration %d: %s Intermediate values: %s, %s%n",
                        count, Arrays.toString(array), array[j], array[i]);
                array[j + 1] = array[j];
                j--;
                count++;
            }
            array[j + 1] = element;
        }
    }

    /**
     * Tests the algorithm using the array <br>
     * <code>Integer[] array = {2, 11, 98, 23, 48, 33, 97, 61, 3}</code>.
     *
     * @param args Console arguments. Not used.
     */
    public static void main(String[] args) {
        Integer[] array = {99, 2, 11, 98, 23, 48, 33, 97, 61, 3};
        System.out.printf("Original array: %s%n%n", Arrays.toString(array));
        InsertionSort.insertionSort(array);
        System.out.printf("%nSorted array:   %s%n", Arrays.toString(array));
    }
}