Check whether array is sorted recursively

Question

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<Integer> test = new ArrayList<>(Arrays.asList(9, 9, 9));
        List<Integer> test2 = new ArrayList<>(Arrays.asList(9, 10, 11));
        List<Integer> test3 = new ArrayList<>(Arrays.asList(5, 5, 3, 7));
        List<Integer> test4 = new ArrayList<>(Arrays.asList(1,2,2,3,3,4));


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

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

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


        int middleIndex = arr.size() / 2 ;
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

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

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

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

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

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

    }

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

}

Answer 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 && isSorted(left) && 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!

Answer 2

An array a is sorted if a[i] <= a[i+1] for 0 <= i < a.size() - 1. For an empty array that is a “vacuous truth” – there are no indices satisfying the condition.

Therefore your functions should return true for an empty array.

Your first function returns false for an empty array, and the second one crashes with an IndexOutOfBoundsException.

More remarks:

• Your function takes a List as parameter, i.e. it can not only be called with an ArrayList but also with other lists (like LinkedList) for which each get(i) has to traverse the list from the head up to position i.

  I'd suggest to either take an array parameter, or to modify it to iterate over the elements instead.

• I do not see an advantage of any recursion. The same task can be achieved with a simple loop.

• You could make the function generic, so that it can not only be used with integer arrays/lists, but also with other (comparable) types.