 # Boost :

Subject: [boost] minmax_element and sorted data
Date: 2009-05-29 10:12:50

I've noticed that minmax_element makes roughly 3n/2 comparisons, though n -
1 comparisons are all that is required to see if data is sorted, and if it
is, the minimum and maximum are known. Sorted data is a relatively common
special-case, and I think minmax_element might be better optimized to take
advantage of sorted data when it is provided. Also, it would be nice to
have a version of it that returns the minimum, maximum, and whether the data
is sorted.
Also worth considering is whether minmax_element can work more efficiently
with long chains of sorted (or reverse-sorted) data, by taking advantage of
the fact that the maximum and minimum of sorted data is known, and it takes
n - 1 comparisons to tell whether a list of n items is sorted.

An example of how sorting can be tested without hurting overall runtime for
unsorted data is how I find the minimum and maximum for integer_sort. Note
that when the data is sorted, it returns with max and min being identical; a
boolean could provide that information in a more general method.
Source:

//Find the minimum and maximum using <
template <class RandomAccessIter>
inline void
find_extremes(RandomAccessIter current, RandomAccessIter last,
RandomAccessIter & max, RandomAccessIter & min)
{
min = max = current;
//It is assumed we have more than 1 element; there are multiple
checks for this
while(!(*(current + 1) < *current)) {
//If everything is in sorted order, return
if(++current == last - 1)
return;
}
//The maximum is the last sorted element
max = current;
//Now that we know it isn't sorted, doing an efficient max/min find
std::pair<RandomAccessIter, RandomAccessIter> vals =
minmax_element(++current, last);
if(*(vals.first) < *min)
min = vals.first;
if(*max < *(vals.second))
max = vals.second;
}