sorting and selection def merge sort( ) """sort the elements of python list using the merge-sort algorithm "" len( if return list is already sorted divide mid / [ :midcopy of first half [mid:ncopy of second half conquer (with recursionsort copy of first half merge sort( sort copy of second half merge sort( merge results merge( smerge sorted halves back into code fragment an implementation of the recursive merge-sort algorithm for python' array-based list class (using the merge function defined in code fragment the running time of merge-sort we begin by analyzing the running time of the merge algorithm let and be the number of elements of and respectively it is clear that the operations performed inside each pass of the while loop take ( time the key observation is that during each iteration of the loopone element is copied from either or into (and that element is considered no furtherthereforethe number of iterations of the loop is thusthe running time of algorithm merge is ( having analyzed the running time of the merge algorithm used to combine subproblemslet us analyze the running time of the entire merge-sort algorithmassuming it is given an input sequence of elements for simplicitywe restrict our attention to the case where is power of we leave it to an exercise ( - to show that the result of our analysis also holds when is not power of when evaluating the merge-sort recursionwe rely on the analysis technique introduced in section we account for the amount of time spent within each recursive callbut excluding any time spent waiting for successive recursive calls to terminate in the case of our merge sort functionwe account for the time to divide the sequence into two subsequencesand the call to merge to combine the two sorted sequencesbut we exclude the two recursive calls to merge sort