binary tree of height can store at most nodes equivalentlya tree with nodes requires at least dlog( ) levels what is the minimum number of nodes that must be in the decision tree for any comparison-based sorting algorithm for valuesbecause sorting algorithms are in the business of determining which unique permutation of the input corresponds to the sorted listall sorting algorithms must contain at least one leaf node for each possible permutation there are npermutations for set of numbers (see section because there are at least nnodes in the treewe know that the tree must have ohm(log !levels from stirling' approximation (section )we know log nis in ohm( log nthe decision tree for any comparison-based sorting algorithm must have nodes ohm( log nlevels deep thusin the worst caseany such sorting algorithm must require ohm( log ncomparisons any sorting algorithm requiring ohm( log ncomparisons in the worst case requires ohm( log nrunning time in the worst case because any sorting algorithm requires ohm( log nrunning timethe problem of sorting also requires ohm( log ntime we already know of sorting algorithms with ( log nrunning timeso we can conclude that the problem of sorting requires th( log ntime as corollarywe know that no comparison-based sorting algorithm can improve on existing th( log ntime sorting algorithms by more than constant factor further reading the definitive reference on sorting is donald knuth' sorting and searching [knu wealth of details is covered thereincluding optimal sorts for small size and special purpose sorting networks it is thorough (although somewhat datedtreatment on sorting for an analysis of quicksort and thorough survey on its optimizationssee robert sedgewick' quicksort [sed sedgewick' algorithms [sed discusses most of the sorting algorithms described here and pays special attention to efficient implementation the optimized mergesort version of section comes from sedgewick while ohm( log nis the theoretical lower bound in the worst case for sortingmany times the input is sufficiently well ordered that certain algorithms can take advantage of this fact to speed the sorting process simple example is insertion sort' best-case running time sorting algorithms whose running time is based on the amount of disorder in the input are called adaptive for more information on adaptive sorting algorithmssee " survey of adaptive sorting algorithmsby estivill-castro and wood [ecw