# Can it be done without creating a new merged array, meaning sorting using only B and A?

• Can it be done without creating a new merged array, meaning sorting using only B and A?

• Yes, you are suppose to merge B into A without using any extra space.

• That was easy if you think out of the box - in reverse :)

• of course, you can just copy B into A, from end to the start

if you're familiar with STL, you can refer to the method of rbegin iterator

• yes, you can do this at runtime:

``````class Solution {
public:
void merge(int A[], int m, int B[], int n) {
for (int idx = m + n - 1; idx >= 0; idx--) {
if (m <= 0) {
A[idx] = B[--n];
} else if (n <= 0) {
break;
} else if (A[m-1] < B[n-1]) {
A[idx] = B[--n];
} else {
A[idx] = A[--m];
}
}
}
};``````

• Yes, Try solve it by fill proper int to array A's tail first.

• ``````class Solution {
public:
void merge(int A[], int m, int B[], int n) {

auto posA = m - 1;
auto posB = n - 1;
auto posWrite =  n + m - 1;

while (posB >= 0 && posA >= 0) {
if (B[posB] < A[posA])
A[posWrite--] = A[posA--];
else
A[posWrite--] = B[posB--];
}

for (; posB >= 0; --posWrite, --posB)
A[posWrite] = B[posB];
}
};``````

• This post is deleted!

• ``````public void merge(int A[], int m, int B[], int n) {
int index=m+n-1;
for(int i=m-1,j=n-1;index>=0;index--) {
if(i>=0&&j>=0) {
if(B[j]>A[i])
A[index] =B[j--];
else
A[index] =A[i--];
} else {
if(j>i)
A[index] =B[j--];
else
A[index] =A[i--];

}
}
}``````

• My solution is almost the same way as those above. Merge from the end. Take care if A[] or B[] is used up. Let me finish it in one line:

``````    void merge(int A[], int m, int B[], int n) {
for(int i=m+n-1;i>=0;i--) A[i]=(m!=0&&(n==0||A[m-1]>B[n-1]))?A[--m]:B[--n];
}``````

• ``````public class Solution {
public void merge(int A[], int m, int B[], int n) {

int total;
int lengthA=m-1;
int lengthB=n-1;

for (total=m+n-1;total>=0;total--){
if (lengthA<0){
A[total]=B[lengthB--];
}else if (lengthB<0){
A[total]=A[lengthA--];
}else if (A[lengthA]>=B[lengthB]){
A[total]=A[lengthA--];
//lengthA--;
}else {
A[total]=B[lengthB--];
//lengthB--;
}
}

}
``````

}

• This post is deleted!

• This post is deleted!

• This post is deleted!

• Look at my in-place merging from the tail of A. I believe it is both simple and easy to understand.

``````public class Solution {
public void merge(int A[], int m, int B[], int n) {
while(m>0 && n>0)
A[m+n-1] = A[m-1] > B[n-1] ? A[--m] : B[--n];
while(n>0)
A[n-1] = B[--n];
}
}``````

• Could be further simplified using one single loop:

``````public class Solution {
public void merge(int A[], int m, int B[], int n) {
while ( n>0){
A[m+n-1] = (m<=0 || A[m-1]< B[n-1] )? B[--n] : A[--m];
}
}
}``````

• Could be further simplified by using one single loop:

``````public class Solution {
public void merge(int A[], int m, int B[], int n) {
while (n>0){
A[m+n-1] = (m<=0 || A[m-1]< B[n-1] )? B[--n] : A[--m];
}
}
}
``````

• It can be accepted in OJ, yet I think it'll be wrong when B[] is over (n = 0) firstly, the remaining elements in B[] wouldn't be merged into A[]. Right?

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.