sorting theorem any comparison-based algorithm to find the minimum and maximum must use at least  / comparisons proof the basic idea is that if two items are unmarkedthe adversary must give out two pieces of information otherwiseone of the items has either or an (perhaps bothin that casewith reasonable carethe adversary should be able to avoid giving out two units of information for instanceif one itemxhas and the other itemyis unmarkedthe adversary lets win again by saying this gives one unit of information for but no new information for it is easy to see thatin principlethere is no reason that the adversary should have to give more than one unit of information out if there is at least one unmarked item involved in the comparison it remains to show that the adversary can maintain values that are consistent with its answers if both items are unmarkedthen obviously they can be safely assigned values consistent with the comparison answerthis case yields two units of information otherwiseif one of the items involved in comparison is unmarkedit can be assigned value the first timeconsistent with the other item in the comparison this case yields one unit of information answer information < < or wl or wl new new unchanged + > or wl unchanged - < or wl unchanged max( yl or or wl > or or wl or or wl unchanged min( ywl wl consistent unchanged unchanged wl wl wl symmetric to an above case figure adversary constructs input for finding the maximum and minimum as algorithm runs