arraysoptimized quicksort performs well because it does one partition step before calling insertion sort compared to the other ( log nsortsunoptimized heapsort is quite slow due to the overhead of the class structure when all of this is stripped away and the algorithm is implemented to manipulate an array directlyit is still somewhat slower than mergesort in generaloptimizing the various algorithms makes noticeable improvement for larger array sizes overallradix sort is surprisingly poor performer if the code had been tuned to use bit shifting of the key valueit would likely improve substantiallybut this would seriously limit the range of element types that the sort could support lower bounds for sorting this book contains many analyses for algorithms these analyses generally define the upper and lower bounds for algorithms in their worst and average cases for most of the algorithms presented so faranalysis is easy this section considers more difficult task -an analysis for the cost of problem as opposed to an algorithm the upper bound for problem can be defined as the asymptotic cost of the fastest known algorithm the lower bound defines the best possible efficiency for any algorithm that solves the problemincluding algorithms not yet invented once the upper and lower bounds for the problem meetwe know that no future algorithm can possibly be (asymptoticallymore efficient simple estimate for problem' lower bound can be obtained by measuring the size of the input that must be read and the output that must be written certainly no algorithm can be more efficient than the problem' / time from this we see that the sorting problem cannot be solved by any algorithm in less than ohm(ntime because it takes at least steps to read and write the values to be sorted based on our current knowledge of sorting algorithms and the size of the inputwe know that the problem of sorting is bounded by ohm(nand ( log ncomputer scientists have spent much time devising efficient general-purpose sorting algorithmsbut no one has ever found one that is faster than ( log nin the worst or average cases should we keep searching for faster sorting algorithmor can we prove that there is no faster sorting algorithm by finding tighter lower boundthis section presents one of the most important and most useful proofs in computer scienceno sorting algorithm based on key comparisons can possibly be faster than ohm( log nin the worst case this proof is important for three reasons firstknowing that widely used sorting algorithms are asymptotically optimal is reassuring in particularit means that you need not bang your head against the wall searching for an (nsorting algorithm (or at least not one in any way based on key