Ytukyg

I've written a code that I try to use divide and conquer approach to determine if the given array is sorted. I wonder whether I apply the approach accurately.

public static boolean isSorted(List<Integer> arr, int start, int end) {

    if (end - start == 1) // base case to compare two elements

        return arr.get(end) > arr.get(start);



    int middle = (end + start) >>> 1; // division by two

    boolean leftPart = isSorted(arr, start, middle);

    boolean rightPart = isSorted(arr, middle, end);

    return leftPart && rightPart;

}

To use call,

isSorted(list, 0, list.size() - 1)

It looks like your are doing it mostly right. You have problems with length zero and length 1 arrays, but you should be able to fix those pretty quick.

You may be doing more work than necessary. If an array is not sorted, you might find leftPart is false, but you unconditionally go on to determine the value of rightPart anyway, despite it not mattering. The simplest way to avoid that is to combine that recursive calls and the && operation. Ie:

return isSorted(arr, start, middle) && isSorted(arr, middle, end);

Lastly, if the array contains duplicates, can it still be considered sorted? You return false for [1, 2, 2, 3].