## Merge two sorted arrays

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

My initial thoughts:
This is part of the merge-sort. Denote the size of $A$ as $m$ and size of $B$ as $n$, then we have a $O(m+n)$ linear algorithm.

My initial codes:

```	public static int[] merge(int[] A, int[] B) {
int i = 0;
int j = 0;
int[] merged = new int[A.length + B.length];
int index = 0;
while (i != A.length && j != B.length) {
if (A[i] <= B[j]) {
merged[index++] = A[i];
i++;
} else {
merged[index++] = B[j];
j++;
}
}
if (i != A.length) {
for (int m = i; m < A.length; ++m)
merged[index++] = A[m];
}
if (j != B.length) {
for (int m = j; m < B.length; ++m)
merged[index++] = B[m];
}
return merged;
}

It takes $O(m+n)$ additional space. Plus, I don’t utilize the fact that $A$ has a large enough buffer at the end to hold $B$.
Solution:
public static void bufferMerge(int[] A, int[] B,
// Assume sizeAdata + sizeB = A.length
// i.e., B exactly fits into the buffer at the end of A
int k = A.length - 1; // Index of last location of array A
int i = sizeAdata - 1;// Index of last element in array A
int j = sizeB - 1;// Index of last element in array B

// Start comparing from the last element and merge A and B
while (i >= 0 && j >= 0) {
if (A[i] > B[j]) {
A[k--] = A[i--];
} else {
A[k--] = B[j--];
}
}
while (j >= 0) {
A[k--] = B[j--];
}
}

Highlighted line 17. We don’t need to consider the case where $j$ reaches 0 where $i$ is still greater than 0. In that case, it means array $A$ has some leading elements left. Then we don’t need to move them because:

All of them must be less the smallest element in $B$. So they should still be in the leading positions to maintain the ordering.
As we assume the size of elements in A + size of B = size of A, we don’t have any empty positions. Therefore those elements should be sitting exactly the same positions as before. (We don’t need to shift them to the right)

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b2deaf1d6f97', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b2deaf1d6fce',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b2deaf1d6fd0',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});