otherwiseboth items involved in the comparison are marked if both are wlthen we can answer consistently with the current assignmentyielding no information otherwiseat least one of the items has only an or only we will allow that item to compare redundantly (if it is an then it loses againif it is then it wins again)and its value can be easily adjusted if neededbased on the other item in the comparison (an can be lowered as neededa can be raised as neededthis yields at most one unit of information for the other item in the comparisonpossibly zero figure summarizes the action of the adversarymaking the primary element whose value changes in all cases at most / comparisons yield two units of informationmeaning that the remaining informationnamely / unitsmust each be obtained one comparison at time thus the total number of comparisons that are needed is at least /  / it is easy to see that this bound is achievable pair up the elementsand perform comparison between each pair then find the maximum among the winners and the minimum among the losers linear-time sortsbucket sort and radix sort although we proved in section that any general sorting algorithm that uses only comparisons requires ( log ntime in the worst caserecall that it is still possible to sort in linear time in some special cases simple example is bucket sort for bucket sort to workextra information must be available the input an must consist of only positive integers smaller than (obviously extensions to this are possible if this is the casethen the algorithm is simplekeep an array called countof size mwhich is initialized to all thuscount has cellsor bucketswhich are initially empty when ai is readincrement count[ai by after all the input is readscan the count arrayprinting out representation of the sorted list this algorithm takes ( )the proof is left as an exercise if is ( )then the total is (nalthough this algorithm seems to violate the lower boundit turns out that it does not because it uses more powerful operation than simple comparisons by incrementing the appropriate bucketthe algorithm essentially performs an -way comparison in unit time this is similar to the strategy used in extendible hashing (section this is clearly not in the model for which the lower bound was proven this algorithm doeshoweverquestion the validity of the model used in proving the lower bound the model actually is strong modelbecause general-purpose sorting algorithm cannot make assumptions about the type of input it can expect to see but must it is possible that the current assignment for both items has the same numberin such case we can increase all items whose current value is larger than by and then add to to break the tie