Merge two sorted arrays

13.cpp

// Merge two sorted arrays
// http://www.geeksforgeeks.org/merge-one-array-of-size-n-into-another-one-of-size-mn/
// Time complexity: 0(m+n)

void merge(A, B){
  int k=0;
  for(int i=m; i<m+n; i++)A[i] = B[k];
  k=0;
  i=0;j=m;
  while(k < (m+n)){
    if(A[i] > B[j]){
      A[k] = A[i];
      i++;
      k++;
    }
    else {
      A[k] = B[j];
      k++;
      j++;
    }
  }
}