Here is the algorithm (assumes n even):
void minMax( vector<int> & data, pair<int, int> & result ) { int i = 0; int curmax = data[i]; int curmin = data[i+1]; if( curmax < curmin ) { curmax = data[i+1]; curmin = data[i]; } int max = curmax; int min = curmin; for( i = 2; i < data.size(); i += 2 ) { curmax = data[i]; curmin = data[i+1]; if( curmax < curmin ) { curmax = data[i+1]; curmin = data[i]; } if( curmax > max ) max = curmax; if( curmin < min ) min = curmin; } result.first = min; result.second = max; }
Computes min-max in pairs. Only need to compare current min to min and current max to max. How many comparisons all together?