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 as and size of as , then we have a 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;
}

**Comments after running:**

It takes additional space. Plus, I don’t utilize the fact that has a large enough buffer at the end to hold .

**Solution:**

public static void bufferMerge(int[] A, int[] B,
int sizeAdata, int sizeB) {
// 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--];
}
}

Comments:

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

- All of them must be less the smallest element in . 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)

### Like this:

Like Loading...

*Related*