Merge two stored arrays with different sizes.

By | March 26, 2017 | 46 Views

1. Question.

You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. For example:

  • int[] a = {2, 3, 4, 8, 10, 100, 0, 0, 0, 0};
  • int[] b = {1, 4, 7, 9};
  • After merged: int[] a = {1, 2, 3, 4, 4, 7, 8, 9, 10, 100}

2. Analysis.

Simply, we compare each of element of array A to array B. If the element value of array A is greater than value of element of array B, we copy the element of array B to temporary array (same size of A) and increase index of array B. Otherwise, the temporary array hold the element of A and increase index of array A. We repeat the process until end of the size of A. Noticeable that we should guarantee out of index of array B.

We increase next place holder in array temp and check it again.

3. Implementation.

The tentative Java implementation as follow:

int[] merge(int[] a, int[] b) {
		// Creating a temporary array has the same size with array a.
		int[] temp = new int[a.length];
		int i = 0, j = 0;
		// Loop each element in arrays a b. 
		for(int k = 0; k < temp.length; k++) {
			// Make sure that we don't check b if no more elements
			if(j < b.length && b[j] <= a[i]) {
				// Copy value of array b to the temporary array.
				temp[k] = b[j];
				// increase b index.
				j ++;
			} else {
				// Copy value of  array a to the temporary array.
				temp[k] = a[i];
				// increase a index.
				i ++;
			}
		}
		return temp;
	}

 

Leave a Reply

Your email address will not be published. Required fields are marked *