Consider the pseudo-code below for merge sort. Re-write the for-loop as a while loop in the merge sort pseudo-code. (You do not need to show the modified while-loop merge sort.) Then count how many lines need to execute to sort the array [3, 2, 1] for both algorithms. Show some work to receive full (and partial) credit. Only count lines the computer thinks on. Note: for merge sort, do not count the function calls, splits or array creation. Just the number of lines inside the merge function. Also, assume no work needs to be done merging a size 1 and 0 array. (Example: sorting [2, 1] merge = 14 lines.)

Also, find an exact formula for the number of lines needed to be run in both the insertion sort and merge sort pseudo-code. This formula should be for arrays of size n that are in the reverse of sorted (e.g. [8, 7, 6, 5, 4, 3, 2, 1] with n = 8). Give the ranges of n where merge sort performs better than insertion sort. For full points, you cannot use a recursively defined function for merge sort.

TopDownMerge(AL, iBegin, iMiddle, iEnd, BI]) i = iBegin, J = iMiddle ; 1 wnLe unere are elements in the left or right runs.. for (k= iBegin; k = iEnd 11 A[1]