Checking whether given array is sorted by divide-and-conquer

Question

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)

• Martin R: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• vnp: Test your code on 3, 4, 1, 2.
• AJNeufeld: @vnp isSorted(list, 0, 3) will call isSorted(arr, 1, 3) which will call isSorted(arr, 1, 2) which will return false. That test case is fine.

Answer 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].