Let A and B be two sorted arrays, each of length n. The operation Merge(A,B) ret

Question

Let A and B be two sorted arrays, each of length n. The operation Merge(A,B) returns a new array of length 2n that contains all the elements of both A and B in sorted order. For example, the merge of {1, 3} with {2, 4} is {1, 2, 3, 4}. (It should be reasonably clear how to write a divide-and-conquer sorting algorithm around Merge.)

(a) Sketch the decision tree that implements a comparison-based Merge algorithm on two arrays, each of length 2, using only the < operator. (You don’t have to match any particular merge pseudocode found elsewhere.)

(b) Let I(n) be the number of ways to interleave two arrays of n elements (i.e. the number of possible ways to merge the two arrays without changing the order of either). Argue that I(n) = (2n) C n.

(c) Argue that log2 (I(n)) = 2n g(n), where g(n) is some function whose growth is o(n).

(d) Suppose we wish to implement Merge using only comparison operations; that is, the only test we are allowed to do is to compare the values of two elements. Use a decision-tree argument and the result of part (b) to show that any implementation of merging requires (n) operations.

Explanation / Answer

Assume, that both arrays are sorted in ascending order and we want resulting array to maintain the same order. Algorithm to merge two arrays A[0..m-1] and B[0..n-1] into an array C[0..m+n-1] is as following:

Introduce read-indices i, j to traverse arrays A and B, accordingly. Introduce write-index k to store position of the first free cell in the resulting array. By default i = j = k = 0.

At each step: if both indices are in range (i < m and j < n), choose minimum of (A[i], B[j]) and write it to C[k]. Otherwise go to step 4.

Increase k and index of the array, algorithm located minimal value at, by one. Repeat step 2.

Copy the rest values from the array, which index is still in range, to the resulting array.

the time complexity depends upon the length of array O(m+n).

#include <iostream>

#include <iostream>

   using namespace std;

   void merge(int* ar1, int* ar2, int ar1Size, int ar2Size);

   int main() {

            int ar1[] = {1, 2};

            int ar2[] = {3, 4};

            merge(ar1, ar2, sizeof(ar1)/sizeof(int), sizeof(ar2)/sizeof(int));

            for(int i = 0; i < sizeof(ar1)/sizeof(int); i++)

                    cout<<ar1[i]<<" ";

            return 0;

   }

   void merge(int* ar1, int* ar2, int ar1Size, int ar2Size)

   {

            for(int i = 0, j = ar1Size-ar2Size; i < ar2Size; i++, j++)

            {

                    ar1[j] = ar2[i];

            }

   }

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.