// -------------------
// InsertionSort1.java
// -------------------

import java.util.Arrays;

final class InsertionSort1 {
    /**
     * O(1)           in space
     * O(n^2) -> O(n) in time
     * stable
     */
    public static void eval (long[] a, int b, int e) {
        assert b <= e;
        if (b == e)
            return;
        final int p = b;
        ++b;
        while (b != e) {
            ++b;
            Insert1.eval(a, p, b);
            assert(IsSorted.eval(a, p, b));}}}

final class InsertionSort1Test {
    public static void main (String[] args) {
        System.out.println("InsertionSort1.java");

        {
        final long[] a = {5, 4, 3, 2, 1};
        InsertionSort1.eval(a, 1, 4);
        assert IsSorted.eval(a, 1, 4);
        assert Arrays.equals(a, new long[] {5, 2, 3, 4, 1});
        }

        for (int i = 0; i != 10; ++i) {
            final long[] a = new long[1000];
            RandomFill.eval(a, 0, a.length);
            InsertionSort1.eval(a, 0, a.length);
            assert IsSorted.eval(a, 0, a.length);}

        System.out.println("Done.");}}