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 lichenga2...@gmail.com 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
