The Python function mergesort recursively sorts a list of numbers U using a recursive divide-and-conquer algorithm, then returns a sorted list S. The function head returns the first element of a nonempty list Q, and the function tail returns all but the first element of a nonempty list Q. Lines 06–07 detect if U is trivially sorted. Lines 09–16 split U into two halves, L and R, of approximately equal lengths. Lines 17–18 recursively sort L and R. Lines 19–28 merge the sorted L and R back into a sorted list S.

Prove that mergesort’s splitting loop is correct (lines 09-16). Do not prove that the rest of the mergesort is correct. You must use a loop invariant. Your proof must have three parts: initialization, maintenance and termination.

1. Find a loop invariant for the splitting loop
2. 
   
3. Use loop invariant to prove the initialization part
4. 
   
5. Use loop invariant to prove the maintenance part
6. 
   
7. Use loop invariant to prove the termination part
8. 
   
9. Find the worst case run time of mergesort’s merging loop(lines 19-28). Do not find the run time for the rest of mergesort. Your answer must define T(n) where n is the number of elements to be sorted.

 

01 def head(Q): 02 return Q[0] 03 def tail(Q): 04 return Q[1:] 05 def mergesort (U): if U =- [] or tail (U) 06 =- (): 07 return U 08 else: 09 L = [) 10 R = while U !- U and tai1(U) != []: L = L + [head (U)] U - tail(U) R = R + [head (U)] U = tail(U) 11 12 13 14 15 16 L = L + U L = mergesort (L) R = mergesort (R) 17 18 19 S = [) while L I- [] and R != []: if head(L)