# Best algorithm to check whether a vector is sorted

### Question

What would be the best way to check that a `std::vector` is sorted? Is there something faster than a loop checking that `v[i]<=v[i+1]`? Is it faster/cleaner with iterators? Or is it actually better to just call `sort` every time (though the "v is already sorted" case is quite common)?

We can safely assume the vector only contains PODs, usually `float`s and sometimes `double`s and `int`s.

The size of the vector is non-trivial (usually a few thousands items) but not extreme (not gigabyte-sized).

• in some instances we'll sort the vector immediately afterwards, however there are other instances where we don't (it's an error case of our algorithm).
• we already use a flag "IsSorted" whenever possible.
1
18
10/11/2011 1:20:40 PM

Consider Multiple Cpu Cores

It depends on your platform and number of items in the vector. You'd have to benchmark to find what's best.

It's not possible to answer: Is there something faster than a loop checking that v[i]<=v[i+1] ?
With: No.

Because... computers now a days have multiple cpus/cores/hyperthreading. So, it may well be a lot quicker to exploit the parallism in the computer by spliting the work of checking to a number of threads, so each cpu can be checking a small range in parallel.

It's probably best to do this via a library function rather than implementing it yourself. New versions of libraries will exploit parallism. So, if you go for a std::sort you'll probably find when you build against newer implementations of STL, they'll do the operation in parallel for you without you having to worry about it. I don't know if there are readily available versions of STL that do this already, but it's worth sticking to the library functions so that when you upgrade to a version that does, this optimization is there for you without you needing to make any changes.

16
11/4/2008 4:57:26 PM

Is there something faster than a loop checking that v[i]<=v[i+1] ?

No.

If this is something you wish to check often, you might want to make a wrapper class that keeps a "sorted" flag which starts out False, is set to False whenever an item is added, and add a member function sort() that sets the flag to True after sorting.