Wednesday, May 11, 2011

Given two sorted arrays of size m and n respectively (m >> n), how to merge them together?


Given two sorted arrays of size m and n respectively (m >> n),  how to merge them together? 
(Note: if you try to insert n numbers to the larger array to obtain O(n \log m) complexity, pay attention that you have to move elements around for insertions. Also, simply merging those two arrays is not the optimal solution here.) 

Solution
Consider A[m+1] and B[n+1] and C[m+n] (m>>n and indexing starts from 1)
Instead of merging the 2 arrays from front end, merge them in the reverse direction-considering the largest elements(A[m] and B[n]) from both the arrays and inserting it at the (m+n)th position of A and so on.

int firstArr=m;
int secondArr=n;


for(insertPosition=m+n;i>=1;i--)
{
  if(m==-1)
  { //Transfer all remaining elements from B to C;}
  else if(n==-1)
  { //Transfer all remaining elements from A to c; }
  else
  {
    if(A[firstArr]>=B[secondArr])
    C[insertPos]=A[firstArr--];
    else C[insertPos]=B[secondArr--]
  }
} 

0 comments:

Post a Comment