3
\$\begingroup\$

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)
\$\endgroup\$
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Martin R Nov 24 '18 at 22:24
  • \$\begingroup\$ Test your code on 3, 4, 1, 2. \$\endgroup\$ – vnp Nov 25 '18 at 6:43
  • \$\begingroup\$ @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. \$\endgroup\$ – AJNeufeld Nov 25 '18 at 18:02
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.