page 7

Code for Insertion Sort
//time: O(N) to O(N*N), extra space: O(1)
public class Insertion {
    public static void insertion(Comparable[] a) {
        for(int i = 0; i < a.length; i++) {
            for(int j = i; j >0 && less(a[j], a[j-1]; j--) exch(a, j, j-1);
        }
    }
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }
    private static exch(int[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    public static boolean isSorted(Comparable[] a) {
        for(int i = 1; i < a.length; i++) {
            if(less(a[i], a[i - 1])) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        String[] a = new String[]{"xyx", "code", "network", "cyber", "cyberjedizen", "kl2217"};
        sort(a);
        assert isSorted(a);
    }
}