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

Find the worst case run time of mergesorts merging loop (lines 1928). Do not find the run time for the rest of mergesort. Do not use O, , or . Your answer must define T(n) where n is the number of elements to to be sorted. Like the example in Cormens text, assume that the run times of lines 19, 20 ..., 28 are constants c, c ..., c, respectively. All these constants are greater than 0, and some of them may be equal. Also assume that head, tail, and list concatenation all work in constant time. (These assumptions may not be true for real Python code, but make them anyway. Consider negative and even cases.