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 0607 detect if U is trivially sorted. Lines 0916 split U into two halves, L and R, of approximately equal lengths. Lines 1718 recursively sort L and R. Lines 1928 merge the sorted L and R back into a sorted list S.

Code:

01 def head(Q): 02 return Q[0] 03 def tail(Q): 04 return Q[1:] 05 def mergesort(U): 06 if U == [] or tail(U) == []: 07 return U 08 else: 09 L = [] 10 R = [] 11 while U != [] and tail(U) != []: 12 L = L + [head(U)] 13 U = tail(U) 14 R = R + [head(U)] 15 U = tail(U) 16 L = L + U 17 L = mergesort(L) 18 R = mergesort(R) 19 S = [] 20 while L != [] and R != []: 21 if head(L) <= head(R): 22 S = S + [head(L)] 23 L = tail(L) 24 else: 25 S = S + [head(R)] 26 R = tail(R) 27 S = S + L + R 28 return S

Question:

Prove that mergesorts splitting loop is correct (lines 09-16) by find a loop invariant.

Thank you!!!