## Friday, March 28, 2014

### Problem

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.
Another way to ask same question
Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2), merge them to get a sorted array of size 2n. Do this in linear time and in-place.

### Example

array1 = {1, 3, 6}
array2 = {2, 4, 5, _, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

### Solution

Method 1 - Merge sort
This is part of the merge-sort. Let the position of the last element located in the 2 arrays is called tail. Also, for array B, end is same as tail of the array. We start with tails of the 2 arrays, and compare the 2 elements and put them at the end of the array A, whichever is maximum.

Code in java
```public static void bufferMerge(int[] A, int[] B, int sizeAdata) {
// Assume sizeAdata + sizeB = A.length
// i.e., B exactly fits into the buffer at the end of A
int aEnd = A.length - 1; // Index of last location of array A
int aTail = sizeAdata - 1;// Index of last element in array A
int bTail = B.length - 1;// Index of last element as well as
//last location in array B

// Start comparing from the last element and merge A and B
while (aTail >= 0 && bTail >= 0) {
if (A[aTail] > B[bTail]) {
A[aEnd--] = A[aTail--];
} else {
A[aEnd--] = B[bTail--];
}
}
while (bTail >= 0) {
A[aEnd--] = B[bTail--];
}
}
```

Time Complexity - O (m+n) where size of A as m and size of B as n. So , a linear time algorithm.

Similar Problem:

Question : Given a sorted array of size n with n elements (array1) and a sorted array of size 2n with n elements (array2) which are scattered throughout the array, merge them to get a sorted array of size 2n. Do this in linear time and in-place.

Example:
array1 = {1, 3, 6}
array2 = {2, _,4 , 5, _, _}
sortedArray = {1, 2, 3, 4, 5, 6}

Again solution is same as above, but first make array 2 to skip all the whitespaces and make it like this:
array2 = {2, ,4 , 5, _, _,_}