while len(left_halfand len(right_half)if left_half[iright_half[ ]a_list[kleft_half[ii elsea_list[kright_half[jj while len(left_half)a_list[kleft_half[ii while len(right_half)a_list[kright_half[jj print("merging "a_list a_list [ merge_sort(a_listprint(a_listonce the merge_sort function is invoked on the left half and the right half (lines - )it is assumed they are sorted the rest of the function (lines - is responsible for merging the two smaller sorted lists into larger sorted list notice that the merge operation places the items back into the original list (a_listone at time by repeatedly taking the smallest item from the sorted lists the merge_sort function has been augmented with print statement (line to show the contents of the list being sorted at the start of each invocation there is also print statement (line to show the merging process the transcript shows the result of executing the function on our example list note that the list with and will not divide evenly the first split gives [ and the second gives [ it is easy to see how the splitting process eventually yields list that can be immediately merged with other sorted lists in order to analyze the merge_sort functionwe need to consider the two distinct processes that make up its implementation firstthe list is split into halves we already computed (in binary searchthat we can divide list in half log times where is the length of the list the second process is the merge each item in the list will eventually be processed and placed on the sorted list so the merge operation which results in list of size requires operations the result of this analysis is that log splitseach of which costs for total of log operations merge sort is an ( log nalgorithm recall that the slicing operator is (kwhere is the size of the slice in order to guarantee that merge_sort will be ( log nwe will need to remove the slice operator againthis is possible if we simply pass the starting and ending indices along with the list when we make the recursive call we leave this as an exercise it is important to notice that the merge_sort function requires extra space to hold the two sorting and searching