Check whether array is sorted recursively I'm trying to implement isSorted method checking whether given array is sorted recursively. I've written two types, one is similar to merge sort logic, the another is like loop. Can they be made more efficient? Is there any thing I overlooked?

class SortedRecursive {
    public static void main(String[] args) {
        List&lt;Integer&gt; test = new ArrayList&lt;&gt;(Arrays.asList(9, 9, 9));
        List&lt;Integer&gt; test2 = new ArrayList&lt;&gt;(Arrays.asList(9, 10, 11));
        List&lt;Integer&gt; test3 = new ArrayList&lt;&gt;(Arrays.asList(5, 5, 3, 7));
        List&lt;Integer&gt; test4 = new ArrayList&lt;&gt;(Arrays.asList(1,2,2,3,3,4));


        System.out.println("test(nlogn) -&gt; " + isSorted(test));
        System.out.println("test(n) -&gt; " + isSortedAnotherVersion(test, 0));
        System.out.println("test2(nlogn) -&gt; " + isSorted(test2));
        System.out.println("test2(n) -&gt; " + isSortedAnotherVersion(test2, 0));
        System.out.println("input(nlogn) -&gt; " + isSorted(test3));
        System.out.println("input(n) -&gt; " + isSortedAnotherVersion(test3, 0));
        System.out.println("output(nlogn) -&gt; " + isSorted(test4));
        System.out.println("output(n) -&gt; " + isSortedAnotherVersion(test4, 0));
    }

    public static boolean isSorted(List&lt;Integer&gt; arr) {
        if (arr == null || arr.size() == 0) {
            return false;
        }

        if (arr.size() == 1) {
            return true;
        }


        int middleIndex = arr.size() / 2 ;
        List&lt;Integer&gt; left = new ArrayList&lt;&gt;();
        List&lt;Integer&gt; right = new ArrayList&lt;&gt;();

        for (int i = 0; i &lt; middleIndex; i++) {
            left.add(arr.get(i));
        }

        for (int i = middleIndex; i &lt; arr.size(); i++) {
            right.add(arr.get(i));
        }

        //System.out.println("left -&gt; " + left + " right -&gt; " + right);

        boolean result = left.get(middleIndex - 1) &lt;= right.get(0);

        return isSorted(left) &amp;&amp; result &amp;&amp; isSorted(right);

    }

    public static boolean isSortedAnotherVersion(List&lt;Integer&gt; arr, int index) {
        if (arr.size() == 1 || index == arr.size() - 1)
            return true;
        if (arr.get(index) &gt; arr.get(index + 1)) return false;
        return isSortedAnotherVersion(arr, index + 1);
    }

}
Version 1:

Basically OK, but the copying of elements to another list is unnecessary. Have a look at List.sublist on how to create lists from a given index range.

Additionally, you should change the return statement to result &amp;&amp; isSorted(left) &amp;&amp; isSorted(right) so that the recursion does not take place if result is already false. (Look up short-circuiting in logical statements.)

Version 2:

NO. It is much better not to copy the elements and use indexes into the unmodified structure, but here you recurse for every element in the list, i.e. the recursion depth equals the list size. This is a total no-go, as it will definitely blow your stack if we are talking about serious data sizes.

Nevertheless, explore the option of using indexes (maybe a start-index AND an end-index) into the given structure some more and combine it to a divide and conquer-approach as in your first solution.

Happy coding!