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;
 std::advance(middle, std::distance(start, finish)/2);

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

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s