// ------------
// Insert1.java
// ------------

import java.util.Arrays;

final class Insert1 {
    /**
     * O(1)         in space
     * O(n) -> O(1) in time
     * Precondition: [b, e-1) must be sorted
     */
    public static void eval (long[] a, int b, int e) {
        assert b <= e;
        if (b == e)
            return;
        assert IsSorted.eval(a, b, e - 1);
        ++b;
        while (b != e) {
            --e;
            if (a[e - 1] <= a[e])
                return;
            Swap.eval(a, e - 1, e);}}}

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

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

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