is_sorted and is_sorted_until algorithms

This (maybe) traverses the sequence twice instead of once. How about (untested):

    auto &&irel = invokable(rel);
    auto &&iproj = invokable(proj_);
    I i = begin;
    if(begin != end_)
    {
        while(++i != end)
        {
            if(irel(iproj(*i), iproj(*begin)))
                return l;
            begin = i;
        }
    }
    return next_to(i, end_);