Question

Write the algorithm, following the ideas given in class, for merging two sorted arrays into one sorted array. Note the algorithm is not the one for merge sort. 2) What is the best asymptotic upper bound for the algorithm? List reasoning steps.

Answer 1

Algorithm:

1. Let two sorted array be A and B of size m and n respectively.

2. Create a new array C of size m+n

3. initialize-variables i=0,j=0,k=0

4. while I<n and j<m

         if A[i] < B[j]

              C[k] = A[i]

i = i+1, k = k+1

          else

               C[k] = B{j]

i = i+1, k=k+1

5. if i=n meaning all values of array A has been added to C. We need to assigned restover value of array B to C

     while j < m

         C[k] = B[j]

          k=k+1, j=j+1

6. if j=m meaning all values of array B has been added to C. We need to assigned restover value of array A to C

     while i < n

         C[k] = A[j]

          k=k+1, i=i+1

7. C is is merged array formed by merging two sorted array A and B

The asymptotic upper bound for the algorithm will be O(m+n).

This is because all the assignment operator takes constant time and loop is looping for m+n times. In this algorithm, we will get time complexity of a + b*(m+n) where a and b are positive constants and a represent assignment operation time and b times assignment operation in each loop for m+n times so b*(m+n). Hence, the asymptotic upper bound for the algorithm will be O(m+n).