the initial cn term is the cost of doing the findpivot and partition stepsfor some constant the closed-form solution to this recurrence relation is th( log nthusquicksort has average-case cost th( log nthis is an unusual situation that the average case cost and the worst case cost have asymptotically different growth rates consider what "average caseactually means we compute an average cost for inputs of size by summing up for every possible input of size the product of the running time cost of that input times the probability that that input will occur to simplify thingswe assumed that every permutation is equally likely to occur thusfinding the average means summing up the cost for every permutation and dividing by the number of inputs ( !we know that some of these ninputs cost ( but the sum of all the permutation costs has to be ( !)( ( log )given the extremely high cost of the worst inputsthere must be very few of them in factthere cannot be constant fraction of the inputs with cost ( evensay of the inputs with cost ( would lead to an average cost of ( thusas growsthe fraction of inputs with high cost must be going toward limit of zero we can conclude that quicksort will always have good behavior if we can avoid those very few bad input permutations the running time for quicksort can be improved (by constant factor)and much study has gone into optimizing this algorithm the most obvious place for improvement is the findpivot function quicksort' worst case arises when the pivot does poor job of splitting the array into equal size subarrays if we are willing to do more work searching for better pivotthe effects of bad pivot can be decreased or even eliminated one good choice is to use the "median of threealgorithmwhich uses as pivot the middle of three randomly selected values using random number generator to choose the positions is relatively expensiveso common compromise is to look at the firstmiddleand last positions of the current subarray howeverour simple findpivot function that takes the middle value as its pivot has the virtue of making it highly unlikely to get bad input by chanceand it is quite cheap to implement this is in sharp contrast to selecting the first or last element as the pivotwhich would yield bad performance for many permutations that are nearly sorted or nearly reverse sorted significant improvement can be gained by recognizing that quicksort is relatively slow when is small this might not seem to be relevant if most of the time we sort large arraysnor should it matter how long quicksort takes in the rare instance when small array is sorted because it will be fast anyway but you should notice that quicksort itself sorts manymany small arraysthis happens as natural by-product of the divide and conquer approach