Find the min and max elements of a collection, and check whether it is sorted
The quick exit seems a bit clunky.

// 0 or 1 elements
if (first == last) return result;
auto next = std::next(first);
if (next == last) return result;


I also don't like the return on the same line as the if (test) it makes it harder to read (subjective).

I think I would simplify like this:

auto next = first;
if ((next == last) || (++next == last)) {
    return {first, first, last};
}


This also removed the need to declare result so far before it is actually needed.

Thus this:

// The range is not sorted, use a regular minmax_element algorithm
result.min = first;
result.max = current;
result.sorted_until = next;


can now be replaced with:

result_type result = { first, current, next };


Lets also use the std library to convey meaning for the min and max. So this:

if (compare(*tmp.first, *result.min)) {
    result.min = tmp.first;
}
if (not compare(*tmp.second, *result.max)) {
    result.max = tmp.second;
}


Can be replaced by:

auto iterCompare = [&amp;compare](ForwardIterator lhs, ForwardIterator rhs){return compare(*lhs, *rhs);};
result.min = std::min(tmp.first,  result.min, iterCompare); 
result.max = std::max(tmp.second, result.max, iterCompare);