sorting if we choose (log log log )then the number of heaps that have cost sequence less than is at most ( / ) and the theorem follows from our earlier comments using more complex argumentit can be shown that heapsort always uses at least log (ncomparisons and that there are inputs that can achieve this bound the average-case analysis also can be improved to log (ncomparisons (rather than the nonlinear second term in theorem mergesort we now turn our attention to mergesort mergesort runs in ( log nworst-case running timeand the number of comparisons used is nearly optimal it is fine example of recursive algorithm the fundamental operation in this algorithm is merging two sorted lists because the lists are sortedthis can be done in one pass through the inputif the output is put in third list the basic merging algorithm takes two input arrays and ban output array cand three countersactrbctrand cctrwhich are initially set to the beginning of their respective arrays the smaller of [actrand [bctris copied to the next entry in cand the appropriate counters are advanced when either input list is exhaustedthe remainder of the other list is copied to an example of how the merge routine works is provided for the following input actr bctr cctr if the array contains and contains then the algorithm proceeds as followsfirsta comparison is done between and is added to cand then and are compared actr bctr cctr is added to cand then and are compared actr bctr cctr