chap internal sorting comparisonssecondthis proof is one of the few non-trivial lower-bounds proofs that we have for any problemthat isthis proof provides one of the relatively few instances where our lower bound is tighter than simply measuring the size of the input and output as suchit provides useful model for proving lower bounds on other problems finallyknowing lower bound for sorting gives us lower bound in turn for other problems whose solution could be used as the basis for sorting algorithm the process of deriving asymptotic bounds for one problem from the asymptotic bounds of another is called reductiona concept further explored in except for the radix sort and binsortall of the sorting algorithms presented in this make decisions based on the direct comparison of two key values for exampleinsertion sort sequentially compares the value to be inserted into the sorted list until comparison against the next value in the list fails in contrastradix sort has no direct comparison of key values all decisions are based on the value of specific digits in the key valueso it is possible to take approaches to sorting that do not involve key comparisons of courseradix sort in the end does not provide more efficient sorting algorithm than comparison-based sorting thusempirical evidence suggests that comparison-based sorting is good approach the proof that any comparison sort requires ohm( log ncomparisons in the worst case is structured as follows firstyou will see how comparison decisions can be modeled as the branches in binary tree this means that any sorting algorithm based on comparisons can be viewed as binary tree whose nodes correspond to the results of making comparisons nextthe minimum number of leaves in the resulting tree is shown to be the factorial of finallythe minimum depth of tree with nleaves is shown to be in ohm( log nbefore presenting the proof of an ohm( log nlower bound for sortingwe first must define the concept of decision tree decision tree is binary tree that can model the processing for any algorithm that makes decisions each (binarydecision is represented by branch in the tree for the purpose of modeling sorting algorithmswe count all comparisons of key values as decisions if two keys are compared and the first is less than the secondthen this is modeled as left branch in the decision tree in the case where the first value is greater than the secondthe algorithm takes the right branch figure shows the decision tree that models insertion sort on three input values the first input value is labeled xthe second yand the third they are the truth is stronger than this statement implies in realityradix sort relies on comparisons as well and so can be modeled by the technique used in this section the result is an ohm( log nbound in the general case even for algorithms that look like radix sort