The Python function mergesort recursively sorts a list of numbers U using a recursive divide-and-conquer algorithm, then

Fantastic news! We've Found the answer you've been seeking!

Question:

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.

01 def head (Q): 02 return QI0] 03 def tail(Q): 04 return Q[1:] 05 def mergesort (U): 06 if U-= [ ] or tail (U)-[]: 07 08 els

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.

Find a loop invariant for the splitting loop
Use loop invariant to prove the initialization part
Use loop invariant to prove the maintenance part
Use loop invariant to prove the termination part
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.