Solution to LeetCode Problems: Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Thoughts:
A direct solution is, allocate an array with length [m+n] and merge. Then copy the merged array to the original array A. I strongly doubt if it would be the expected answer.

Let's assume only O(1) space could be used instead. Then we have to consider the exploit of excess space in array A, with length n. We can merge the two arrays there, and when the space is all used up, data at starting of A should be either useless (already merged) or at the right place (if all elements in B are smaller than A).

Then we rotate the array leftwise by m. Such coding can be implemented by three reverses: [0, m+n), [0, n), [n, m+n). This is illustrated in Programming Pearls.

Solution:

1. class Solution {  
2. public:  
3.     void merge(int A[], int m, int B[], int n) {  
4.         // Iterator used through merging  
5.         int merge_A = 0;   
6.         int merge_B = 0;  
7.           
8.         // merge is done at the end of m-th element, A[]  
9.         int merge_iter = m;  
10.           
11.         while(merge_A < m || merge_B < n)  
12.         {  
13.             // check if we reached the end of merge region, if so,   
14.             // start from beginning  
15.             if (merge_iter == m + n)  
16.                 merge_iter = 0;  
17.   
18.             if (merge_A == m)  // merge A is done  
19.                 A[merge_iter++] = B[merge_B++];  
20.             else if (merge_B == n) // merge B is done  
21.                 A[merge_iter++] = A[merge_A++];  
22.             else  
23.                 A[merge_iter++] = (A[merge_A] < B[merge_B] ? A[merge_A++] : B[merge_B++]);  
24.         }  
25.           
26.         // merge is complete, now the array looks like  
27.         // 4567 | 123  
28.         // so we need to reverse it -- ref. Programming Pearls  
29.         reverse(A, A+m);  
30.         reverse(A+m, A+m+n);  
31.         reverse(A, A+m+n);  
32.     }  
33. };