Simple O(n+m), No extra space used (O(1) constant auxiliary space)


#1
void Solution::merge(vector<int> &A, vector<int> &B) {
int n=A.size();
int m=B.size();
A.resize(n+m);

for(int i=n+m-1;i>=m;--i){
    A[i]=A[i-m];
}

int curr=0;
int i=m;
int j=0;
while(i<n+m and j<m){
    if(A[i]<B[j]){
        A[curr]=A[i];
        curr++;
        i++;
    }
    else{
        A[curr]=B[j];
        curr++;
        j++;
    }
}

while(i<n+m){
    A[curr]=A[i];
    curr++;
    i++;
}

while(j<m){
    A[curr]=B[j];
    curr++;
    j++;
}

}