Merge two sorted arrays - One having big enough buffer to hold another

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, _, _,_}