# is_sorted in O(log n) time

Checking if array is sorted is simple, compare consecutive elements to check if next element is greater than the previous element. This takes O(n) time. The possible implementation of std::is_sorted is given as follows:

```template <class ForwardIterator>
bool is_sorted (ForwardIterator first, ForwardIterator last)
{
if (first==last) return true;
ForwardIterator next = first;
while (++next!=last) {
if (*next<*first) // or, if (comp(*next,*first)) for version (2)
return false;
++first;
}
return true;
}```

Here I came with an algorithm which is like quick sort and uses O(log n) time. Here is the implementation.

```#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

template <typename T>
bool check_sorted(T start, T finish, bool sorted = true){
if(start == finish) return true;

if(std::next(start) == finish) return *start <= *finish;

T middle = start;

sorted &= check_sorted(start, middle);
sorted &= check_sorted(middle, finish-1);
return sorted;
}

int main(){
std::vector<int> v(20);
std::iota(v.begin(), v.end(), 1);
bool sorted = check_sorted(v.begin(), v.end());
std::cout << "v is sorted? : " << sorted << '\n';

std::vector<int> v2 {20, 1, 3, 5, 2, 1, 4, 19, 18, 10};
sorted = check_sorted(v2.begin(), v2.end());
std::cout << "v2 is sorted?: " << sorted << '\n';

std::vector<int> v3 {1,1,1,1,1,1,1,1,1,1,1,1,1,1};
sorted = check_sorted(v3.begin(), v3.end());
std::cout << "v3 is sorted?: " << sorted << '\n';

std::vector<int> v4 {10,1,1,1,1,1,1,1,1,1,1,1,1,1};
sorted = check_sorted(v4.begin(), v4.end());
std::cout << "v4 is sorted?: " << sorted << '\n';
}```

## Author: Saurabh Purnaye

VP - Low Latency Developer @jpmchase... Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1