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

## 0 comments:

## Post a Comment