Mergesort combining phase:

24 S = [] 25 while L != [] and R != []: 26 if head(L) <= head(R): 27 S = S + [head(L)] 28 L = tail(L) 29 else: 30 S = S + [head(R)] 31 R = tail(R) 32 S = S + L + R 33 return S

Find the run time of mergesorts combining phase (lines 2433). 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 be sorted. Assume that head, tail, list concatenation +, and list creation [x], work in constant time. (This is probably not true in Python, but assume it anyway!) Like the example in Cormens text, also assume that the run times of lines 24, 25 ..., 33 are constants c, c ..., c. All these constants are greater than or equal to 0.