I frob missed the trick:

You can process the elements two at a time, compare them and then only use the smaller of the two to try to update the minimum and only use the larger of the two to try to update the maximum. This requires about N*3/2 comparisons.

I am not making any claims about practical usability of this trick: It's just a neat little puzzle.

Meh, it is a micro-optimization in the part that doesn't dominate. My hunch is that the added branch would slow things down if you were worried about performance.

As mentioned, there are solutions that require zero comparisons. Keep the collection sorted in the first place and don't worry about it.