// -------------
// IsSorted.java
// -------------

import java.util.Arrays;
import java.util.List;

final class IsSorted {
    /**
     * O(1) in space
     * O(n) in time
     */
    public static boolean eval (long[] a, int b, int e) {
        assert b <= e;
        if (b == e)
            return true;
        --e;
        while (b != e) {
            if (a[b] > a[b + 1])
                return false;
            ++b;}
        return true;}

    /**
     * O(1) in space
     * O(n) in time
     */
    public static boolean eval (Object[] a, int b, int e) {
        assert b <= e;
        if (b == e)
            return true;
        --e;
        while (b != e) {
            if (((Comparable) a[b]).compareTo(a[b + 1]) > 0) // warning: unchecked cast
                return false;
            ++b;}
        return true;}

    /**
     * O(1) in space
     * O(n) in time
     */
    public static boolean eval (List x) {
        final Object[] a = x.toArray();
        return eval(a, 0, a.length);}}

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

        {
        final long[] a = {};
        assert IsSorted.eval(a, 0, a.length);
        }

        {
        final long[] a = {2};
        assert IsSorted.eval(a, 0, a.length);
        }

        {
        final long[] a = {3, 2, 1};
        assert !IsSorted.eval(a, 0, a.length);
        }

        {
        final long[] a = {1, 2, 3};
        assert IsSorted.eval(a, 0, a.length);
        }

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

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