chap lower bounds ( <<<< ( et( ) + this is true for > and > this provides base case that allows us to use induction to prove that > ( < in realitythis algorithm is not practical because its constant factor costs are so high so much work is being done to guarantee linear time performance that it is more efficient on average to rely on chance to select the pivotperhaps by picking it at random or picking the middle value out of the current subarray optimal sorting we conclude this section with an effort to find the sorting algorithm with the absolute fewest possible comparisons it might well be that the result will not be practical for general-purpose sorting algorithm but recall our analogy earlier to sports tournaments in sportsa "comparisonbetween two teams or individuals means doing competition between the two this is fairly expensive (at least compared to some minor book keeping in computer)and it might be worth trading fair amount of book keeping to cut down on the number of games that need to be played what if we want to figure out how to hold tournament that will give us the exact ordering for all teams in the fewest number of total gamesof coursewe are assuming that the results of each game will be "accuratein that we assume not only that the outcome of playing would always be the same (at least over the time period of the tournament)but that transitivity in the results also holds in practice these are unrealistic assumptionsbut such assumptions are implicitly part of many tournament organizations like most tournament organizerswe can simply accept these assumptions and come up with an algorithm for playing the games that gives us some rank ordering based on the results we obtain recall insertion sortwhere we put element into sorted sublist of the first elements what if we modify the standard insertion sort algorithm to use binary