Let L1 and L2 be two lists of numbers sorted in increasing o

Let L1 and L2 be two lists of numbers sorted in increasing order. a. Suppose that L1 and L2 contain n1 and n2 elements respectively. Describe an O(n1 +n2)-time algorithm that combines the elements in L1 and L2 into one list where the elements are still in sorted order. b. Let us call the procedure described in part (a) as the union of the two lists. Suppose we now have k lists L[1], L[2], . . . , L[k] whose elements are also in sorted order. We again want to combine all of them into a single list so that the elements are still in sorted order.

Here’s a simple procedure for doing this: First, take the union of L[1] and L[2]. Then take the union of L[3] and 1 the output of the union of L[1] and L[2]. Then take the union of L[4] and the output of the previous step, etc.

b1. Write the above procedure in pseudocode.

b2. Assuming that L[1], . . . , L[k] all have n elements, what is the running time of this procedure? Your answer should be in terms of n and k.

Solution

1. Pseudocode

sortedList( L1, ..., Lk)

begin

till all lists are scanned call sortedList(L(union of two lists),L[I])

end

sortedList(L1, L2)

Create empty unionList

p points to first element of L1

q points to first element of L2

If p <= q

Begin

Put p in unionList

Move p to next element of L1

End

Else If p > q

Begin

Put q in unionList

Move q to next element of L2

End

begin

end

2. If time to combine two sorted list is O(2n) where n is the length of each list

Then for k such list s time taken would be O(kn)