lower bound on sorting recapping our discussions on sorting to this pointwe have described several methods with either worst-case or expected running time of (nlognon an input sequence of size these methods include merge-sort and quick-sortdescribed in this as well as heap-sortdescribed in section natural question to askthenis whether it is possible to sort any faster than in (nlogntime in this sectionwe show that if the computational primitive used by sorting algorithm is the comparison of two elementsthen this is the best we can do-comparison-based sorting has an ohm(nlognworst-case lower bound on its running time (recall the notation ohm(*from section to focus on the main cost of comparison-based sortinglet us only count the comparisons that sorting algorithm performs since we want to derive lower boundthis will be sufficient suppose we are given sequence ( , ,, - that we wish to sortand assume that all the elements of are distinct (this is not really restriction since we are deriving lower boundwe do not care if is implemented as an array or linked listfor the sake of our lower boundsince we are only counting comparisons each time sorting algorithm compares two elements and (that isit asks"is ?")there are two outcomes"yesor "no based on the result of this comparisonthe sorting algorithm may perform some internal calculations (which we are not counting hereand will eventually perform another comparison between two other elements of swhich again will have two outcomes thereforewe can represent comparison-based sorting algorithm with decision tree (recall example that iseach internal node in corresponds to comparison and the edges from node to its children correspond to the computations resulting from either "yesor "noanswer (see figure it is important to note that the hypothetical sorting algorithm in question probably has no explicit knowledge of the tree we simply use to represent all the possible sequences of comparisons that sorting algorithm might makestarting from the first comparison (associated with the rootand ending with the last comparison (associated with the parent of an external nodejust before the algorithm terminates its execution each possible initial orderingor permutationof the elements in will cause our hypothetical sorting algorithm to execute series of comparisonstraversing path in from the root to some external node let us associate with each external node in tthenthe set of permutations of that cause our sorting algorithm to end up in the most important observation in our lower-bound argument is that each external node in can represent the sequence of comparisons for at most one permutation of the justification for this claim is simpleif two different permutations and of are associated with the same external nodethen there are at least two objects and such that is before in but is after in at the same timethe output associated with must be specific reordering of swith either or appearing before the other but if and both cause the sorting