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; }