permutations and of are associated with the same external nodethen there are at least two objects xi and such that xi is before in but xi is after in at the same timethe output associated with must be specific reordering of swith either xi or appearing before the other but if and both cause the sorting algorithm to output the elements of in this orderthen that implies there is way to trick the algorithm into outputting xi and in the wrong order since this cannot be allowed by correct sorting algorithmeach external node of must be associated with exactly one permutation of we use this property of the decision tree associated with sorting algorithm to prove the following resultproposition the running time of any comparison-based algorithm for sorting an -element sequence is ( log nin the worst case justificationthe running time of comparison-based sorting algorithm must be greater than or equal to the height of the decision tree associated with this algorithmas described above (see figure by the argument aboveeach external node in must be associated with one permutation of moreovereach permutation of must result in different external node of the number of permutations of objects is nn( )( thust must have at least nexternal nodes by proposition the height of is at least log( !this immediately justifies the propositionbecause there are at least / terms that are greater than or equal to / in the product !hencen log log( !>log which is ( log nminimum height ( worst-case running timexi xa xb xc xd log( !xe xg xh xk xl xm xn nfigure visualizing the lower bound for comparison-based sorting