The following code fragment is the combining phase of the procedure MERGESORT, which was discussed in the lectures. It is written in Cormens pseudocode.

1 S = [ ] 2 while L [ ] and R [ ] 3 if HEAD(L) HEAD(R) 4 S = S + [ HEAD(L) ] 5 L = TAIL(L) 6 else 7 S = S + [ HEAD(R) ] 8 R = TAIL(R) 9 S = S + L + R

The variables L, R, and S are lists of integers. The empty list is written as [ ]. Integers in L and R are sorted into nondecreasing order. The code fragment combines L and R into a single list S, which is also sorted into nondecreasing order. The procedure HEAD returns the first element in a list. The procedure TAIL returns a list without its first element. The operator + returns the concatenation of two lists, and [ x ] returns a list with one element x. Assume that HEAD, TAIL, and + execute in constant time for any lists. Assume that [ x ] executes in constant time for any x. Suppose that L + R has n elements. What is the worst case run time T(n) of this code fragment? You must write T(n) as an expression using n and some constants, as Cormen did when he computed the run time of his insertion sort algorithm. Here are some hints.

• You do not know what integers are in L and R.

• You know that either L and R are the same length, or else L has one more integer than R, because of how the splitting phase works.

• You do not know how often HEAD(L) TAIL(R) is true or false, because that depends on the integers in L and R.

• You may assume that the else in line 6 executes in constant time.