[boost] minmax_element and sorted data

Subject: [boost] minmax_element and sorted data
From: Steven Ross (spreadsort_at_[hidden])
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;
    }