I am not sure if this what you are looking for. Assuming that the arrays are sorted in ascending order. Choose one of the 2 arrays as a Reference Array. for each element element in reference array, do a binary search to find all elements that are less than the current element in reference and include them in the result array(and mark the index of the largest among them so that you dont have to consider them in subsequent searches reducing the range of binary search) before including the current element from reference.
If there is no element less than the current element in the other array , then include that current element and move to the next element in reference array. On Sun, Nov 7, 2010 at 3:21 AM, lichenga2404 <[email protected]> wrote: > Suppose we'd like to implement a sorting variant where every element > is compared only a small number of times. > a) devise a divide and conquer algorithm to merge 2 sorted arrays of > length n , which guarantees that every element is included in at most > O(log n ) comparisons. > b) using this modified merge , prove that Merge-Sort will include > element in at most O( (log n)^2) comparisons. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
