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

Problem

Example

Solution

See also