Merge two sorted arrays

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.

My initial thoughts:
This is part of the merge-sort. Denote the size of A as m and size of B as n, then we have a O(m+n) linear algorithm.

My initial codes:

	public static int[] merge(int[] A, int[] B) {
		int i = 0;
		int j = 0;
		int[] merged = new int[A.length + B.length];
		int index = 0;
		while (i != A.length && j != B.length) {
			if (A[i] <= B[j]) {
				merged[index++] = A[i];
				i++;
			} else {
				merged[index++] = B[j];
				j++;
			}
		}
		if (i != A.length) {
			for (int m = i; m < A.length; ++m)
				merged[index++] = A[m];
		}
		if (j != B.length) {
			for (int m = j; m < B.length; ++m)
				merged[index++] = B[m];
		}
		return merged;
	}

Comments after running:
It takes O(m+n) additional space. Plus, I don’t utilize the fact that A has a large enough buffer at the end to hold B.

Solution:

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

		// Start comparing from the last element and merge A and B
		while (i >= 0 && j >= 0) {
			if (A[i] > B[j]) {
				A[k--] = A[i--];
			} else {
				A[k--] = B[j--];
			}
		}
		while (j >= 0) {
			A[k--] = B[j--];
		}
	}

Comments:
Highlighted line 17. We don’t need to consider the case where j reaches 0 where i is still greater than 0. In that case, it means array A has some leading elements left. Then we don’t need to move them because:

  1. All of them must be less the smallest element in B. So they should still be in the leading positions to maintain the ordering.
  2. As we assume the size of elements in A + size of B = size of A, we don’t have any empty positions. Therefore those elements should be sitting exactly the same positions as before. (We don’t need to shift them to the right)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: