kth smallest element is in position (because arrays start at index this destroys the original orderingif this is not desirablethen copy must be made using median-of-three pivoting strategy makes the chance of the worst case occurring almost negligible by carefully choosing the pivothoweverwe can eliminate the quadratic worst case and ensure an (nalgorithm the overhead involved in doing this is considerableso the resulting algorithm is mostly of theoretical interest in we will examine the linear-time worst-case algorithm for selectionand we shall also see an interesting technique of choosing the pivot that results in somewhat faster selection algorithm in practice general lower bound for sorting although we have ( log nalgorithms for sortingit is not clear that this is as good as we can do in this sectionwe prove that any algorithm for sorting that uses only comparisons requires ( log ncomparisons (and hence timein the worst caseso that mergesort and heapsort are optimal to within constant factor the proof can be extended to show that ( log ncomparisons are requiredeven on averagefor any sorting algorithm that uses only comparisonswhich means that quicksort is optimal on average to within constant factor specificallywe will prove the following resultany sorting algorithm that uses only comparisons requires log( !)comparisons in the worst case and log( !comparisons on average we will assume that all elements are distinctsince any sorting algorithm must work for this case decision trees decision tree is an abstraction used to prove lower bounds in our contexta decision tree is binary tree each node represents set of possible orderingsconsistent with comparisons that have been madeamong the elements the results of the comparisons are the tree edges the decision tree in figure represents an algorithm that sorts the three elements aband the initial state of the algorithm is at the root (we will use the terms state and node interchangeably no comparisons have been doneso all orderings are legal the first comparison that this particular algorithm performs compares and the two results lead to two possible states if bthen only three possibilities remain if the algorithm reaches node then it will compare and other algorithms might do different thingsa different algorithm would have different decision tree if cthe algorithm enters state since there is only one ordering that is consistentthe algorithm can terminate and report that it has completed the sort if cthe algorithm cannot do thisbecause there are two possible orderings and it cannot possibly be sure which is correct in this casethe algorithm will require one more comparison every algorithm that sorts by using only comparisons can be represented by decision tree of courseit is only feasible to draw the tree for extremely small input sizes the number of comparisons used by the sorting algorithm is equal to the depth of the deepest