Insertion Sort

The following class shows the state of an array after each pass during an insertion sort.

public class InsertionSorter {
    
    ///////// "helper" methods //////////
    
    private static boolean less(Comparable v, Comparable w) {
        return (v.compareTo(w) < 0);
    }
    
    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    
    public static void printOrder(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(b[i] + "  ");
        }
        System.out.println();
    }

    public static void printIndices(Comparable[] b) {
        for (int i = 0; i < b.length; i++) {
            System.out.print(i + "  ");
        }
        System.out.println();
        for (int i = 0; i < b.length; i++) {
            System.out.print("---");
        }
        System.out.println();
    }
    
    ///////////////////////////////////////
    
    public static void insertionSort(Comparable[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (less(a[j], a[j-1])) {
                    exch(a, j, j-1);
                }
                else {
                    break;
                }
            }
            printOrder(a);
        }
    }
    
    public static void main(String[] args) {
        Character[] a = {'K','R','A','T','E','L','E','P','U','I'};
        
        System.out.println("Order before insertion sort application:");
        printOrder(a);
        System.out.println();
        
        printIndices(a);
        insertionSort(a);
        System.out.println();
        System.out.println("Order after insertion sort application:");
        printOrder(a);
    }
}

Output

The output produced by the code above provides a trace of the insertion sort, showing the state of the array after each "insertion"

Order before insertion sort application:
K  R  A  T  E  L  E  P  U  I  

0  1  2  3  4  5  6  7  8  9
----------------------------
K  R  A  T  E  L  E  P  U  I  
K  R  A  T  E  L  E  P  U  I  
A  K  R  T  E  L  E  P  U  I  
A  K  R  T  E  L  E  P  U  I  
A  E  K  R  T  L  E  P  U  I  
A  E  K  L  R  T  E  P  U  I  
A  E  E  K  L  R  T  P  U  I  
A  E  E  K  L  P  R  T  U  I  
A  E  E  K  L  P  R  T  U  I  
A  E  E  I  K  L  P  R  T  U  

Order after insertion sort application:
A  E  E  I  K  L  P  R  T  U