merge two sorted arrays and find minimum distance between them

gistfile1.cpp

// Given two sorted Array A and B, merge all elements to A (suppose A is large enough)
// Algorithm: scan from end of A and B, moving larger one to it, then move forward untial B is empty
// Later we will find that this code can be slightly modified to find the minimum distance between sorted arrays
void mergeSortedArrays(int *A, int m, int *B, int n) {
        //idea 1: 
        //merge from backward of A
        int endA = m-1, endB = n -1, tail = m+n -1;
        while(endB >= 0 && endA >=0 ){
            if (B[endB] >= A[endA] ) {
                A[tail--]  = B[endB--];
            }
            else { //B[endB] < A[endA]
                A[tail--] = A[endA--];
            }
        }
        //now endA <0 or endB <0
        while(endB >=0 ) { //endA run out, copy B to A
            A[tail--] = B[endB--];
        }
        //if endB<0 (i.e. endA >=0), don't need to move A to A
    }

 // Find the min dist of A entries to B entries
 // Algorithm: When merging two sorted arrays as above, two elements from A and B are compared
 //         The minimum of all the compaorisons is the minimum distance between elements from A and B
void findMinDist(int *A, int m, int *B, int n) {
        //scan from beging; at each comparision, record the dist
        int endA = m-1, endB = n -1, tail = m+n -1;
        int minDist = INT_MAX;
        while(endB >= 0 && endA >=0 ){

          minDist = min(minDist, abs(B[endB] - A[endA]));
          //cout << " dist " << B[endB] << " " <<  A[endA]  << " = " << abs(B[endB] - A[endA]) << endl;
          if (B[endB] >= A[endA] ) {
                tail-- ;  endB--;
          }
          else { //B[endB] < A[endA]
              tail--;
              endA--;
          }
        }
}



// Test 
void printVector(vector<int> &A, const char *str) {
        cout << str;

        for(int i=0; i<A.size(); i++)
                cout << " " << A[i];
        cout << endl;
}
int main()
{
        int m = 30, n = 5;
        vector<int> A;
        vector<int> B;
        for(int i=0; i<m; i++) {
                A.push_back((rand()*rand()) % 300);
        }
        sort(A.begin(), A.end());
        printVector(A, "A: ");
        for(int i=0; i<n; i++) {
                B.push_back((rand() * rand())  % 300);
        }
        sort(B.begin(), B.end());
        printVector(B, "B: ");
        vector<int> C(m+n);
        merge(&A[0], m, &B[0], n, &C[0]);
        printVector(C, "after merging");
        findMinDist(&A[0], m, &B[0], n);
        printVector(C, "after merging");
}