is added to cand then and are compared this proceeds until and are compared actr bctr actr cctr bctr actr cctr bctr cctr is added to cand the array is exhausted actr bctr cctr the remainder of the array is then copied to actr bctr cctr the time to merge two sorted lists is clearly linearbecause at most comparisons are madewhere is the total number of elements to see thisnote that every comparison adds an element to cexcept the last comparisonwhich adds at least two the mergesort algorithm is therefore easy to describe if there is only one element to sortand the answer is at hand otherwiserecursively mergesort the first half and the second half this gives two sorted halveswhich can then be merged together using the merging algorithm described above for instanceto sort the eight-element array we recursively sort the first four and last four elementsobtaining then we merge the two halves as aboveobtaining the final list this algorithm is classic divide-and-conquer strategy the problem is divided into smaller problems and solved recursively the conquering phase consists of patching together the answers divide-and-conquer is very powerful use of recursion that we will see many times an implementation of mergesort is provided in figure the one-parameter mergesort is just driver for the four-parameter recursive mergesort the merge routine is subtle if temporary array is declared locally for each recursive call of mergethen there could be log temporary arrays active at any point close examination shows that since merge is the last line of mergesortthere only needs to be one