advanced sorting subsequences both implementations run in ( log ntime to see how we obtain this resultassume an array of elements is passed to recmergesort(on the first invocation of the recursive function for simplicitywe can let be power of which results in subsequences of equal size each time list is split as we saw in the running time of recursive function is computed by evaluating the time required by each function invocation this evaluation only includes the time of the steps actually performed in the given function invocation the recursive steps are omitted since their times will be computed separately we can start by evaluating the time required for single invocation of the recmergesort(function since each recursive call reduces the size of the problemwe let represent the number of keys in the subsequence passed to the current instance of the function ( represents the size of the entire arraywhen the function is executedeither the base case or the divide and conquer steps are performed the base case occurs when the supplied sequence contains single item ( )which results in the function simply returning without having performed any operations this of course only requires ( time the dividing step is also constant time operation since it only requires computing the midpoint to determine where the virtual sequence will be split the real work is done in the conquering step by the mergevirtuallists(function this function requires (mtime in the worst case where represents the total number of items in both subsequences the analysis for the merging operation follows that of the mergesortedlists(from and is left as an exercise having determined the time required of the various operationswe can conclude that single invocation of the recmergesort(function requires (mtime given subsequence of keys the next step is to determine the total time required to execute all invocations of the recursive function this analysis is best described using recursive call tree consider the call tree in figure which represents the merge sort algorithm when applied to sequence containing keys the values inside the function call boxes show the size of the subsequence passed to the function for that invocation since we know single invocation of the recmergesort(function requires ( figure recursive call tree for the merge sort algorithm for