Divide&Conquer Algorithm for Checking if a list is sorted in Descending order

Question

I need to write a function that checks if an array/list/vector(in R)/ is sorted in Descending order. The answer must be implemented using Divide&Conquer.

Here is what I tried(The Implementation is in R):

is.sort<-function(x){    
  n<-length(x)
  if (n==1)
    return(T)

  mid<-floor(n/2)   
  x1<-is.sort(x[1:mid])
  x2<-is.sort(x[(mid+1):n])
  return(ifelse(x1>=x2,T,F))
}

But thats always returns T :/ Thanks for the Help

Answer 1

It is quite awkward to implement that using D&C. However, let's try.

1. A sequence of length 1 is always sorted.
2. If x is of length >= 2, then divide it into 2 non-empty subsequences x1 and x2. Then x is sorted if x1 is sorted, x2 is sorted, and the last element in x1 is greater than or equal to (assuming a non-increasing ordering) the first element in x2.

This may be implemented as:

is.sort<-function(x){
   n<-length(x)
   if (n==1)
      return(TRUE)
   mid<-floor(n/2)
   return(x[mid] >= x[mid+1] && is.sort(x[1:mid]) && is.sort(x[(mid+1):n]))
}

BTW, R has a is.unsorted function, but it determines only if a sequence is sorted w.r.t. < or <=. For those who miss its >= equivalent here's a trivial Rcpp implementation:

Rcpp::cppFunction('
bool is_sort(NumericVector x) {
   int n=x.size();
   for (int i=0; i<n-1; ++i)
      if (x[i] < x[i+1]) return false;
   return true;
}
')