timewe can determine the time required for each instance of the function based on the size of the subsequence processed by that instance to obtain the total running time of the merge sort algorithmwe need to compute the sum of the individual times in our sample call treewhere the first recursive call processes the entire key list this instance makes two recursive callseach processing half of the original key sequenceas shown on the second level of the call tree the two function instances at the second level of the call tree each make two recursive callsall of which process one-fourth of the original key sequence these recursive calls continue until the subsequence contains single key valueas illustrated in the recursive call tree while each invocation of the functionother than the initial callonly processes portion of the original key sequenceall keys are processed at each level if we can determine how many levels there are in the recursive call treewe can multiply this value by the number of keys to obtain the final run time when is power of the merge sort algorithm requires log levels of recursion thusthe merge sort algorithm requires ( log ntime since there are log levels and each level requires time the final analysis is illustrated graphically by the more general recursive call tree provided in figure when is not power of the only difference in the analysis is that the lowest level in the call tree will not be completely fullbut the call tree will still contain at most dlog ne levels number of levels time per level nn / / / / log / / / / / / / / total timen log figure time analysis of the merge sort algorithm quick sort the quick sort algorithm also uses the divide and conquer strategy but unlike the merge sortwhich splits the sequence of keys at the midpointthe quick sort partitions the sequence by dividing it into two segments based on selected pivot key in additionthe quick sort can be implemented to work with virtual subsequences without the need for temporary storage