Problem Statement

1Problem Description : 
2Given two integer arrays A and B sorted in increasing order, merge A and B into a single sorted array C in increasing order.
3
4Input:  
5Two sorted arrays A and B
6 
7Output: 
8Return merged sorted array C.

Solution Approaches

Naïve Solution

Prerequisite

• Array Data Structure
• Sorting

Algorithm

• Create an array C of length m+n where m is length of array A and n is length of array B.
• Copy elements of A and B into Array C.
• Sort the array C.

Complexity Analysis

• Time Complexity : O( (m+n) log (m+n) ) (Sorting Complexity)
• Space Complexity: O(1)

Using Two Pointers

Prerequisite

• Array Data Structure
• Two Pointer Technique

Algorithm

1Input : Sorted arrays A and B given 
2
3Step 1: Initialize m and n to length of the arrays A and B respectively. 
4
5Step 2: Create empty array C of length m+n. 
6
7Step 3: initialize i, j and k  to index 0 of A, B and C respectively.  
8
9Step 4:  if i < m and j < n , compare A[i] and B[j]    
10  Step 4.1 : if A[i] is lesser than B[j], copy A[i] into C[k] and increment i and k.  
11  Step 4.2 : else copy B[j] into C[k] and increment j and k. 
12
13Step 5: else if i < m copy A[i] into C[k] and increment i and k.
14
15Step 6: else if j < n copy B[j] into C[k] and increment j and k. 
16
17Step 7: Repeat Steps 4 to 6 until we exhaust arrays A and B. 

Example Dry Run

Input : A[] = {1, 3, 5, 6} , B[] = {2, 4, 7}

1Step 1 : m = A.length and n = B.length => A = 4 and B = 3 
2
3Step 2: initialize result array C of length (m+n) which is  7  
4
5Step 3 : initialize i = 0 , j = 0 and k = 0 for arrays A, B and C respectively.  
6
7Step 4 to 6  
8   Iteration 1 :  i = 0, j = 0 and k = 0  
9                  Compare A[0] with B[0]  
10                  here A[0] < B[0] => C[0] = A[0] and i ++, k++  
11
12   Iteration 2 :  i = 1, j = 0 and k = 1  
13                  Compare A[1] with B[0]  
14                  here A[1] > B[0] => C[1] = B[0] and j++, k++  
15
16   Iteration 3 :  i = 1, j = 1 and k = 2  
17                  Compare A[1] with B[1]  
18                  here A[1] < B[1] => C[2] = A[1] and i++, k++  
19
20   Iteration 4 :  i = 2, j = 1 and k = 3  
21                  Compare A[2] with B[1]  
22                  here A[2] > B[1] => C[3] = B[1] and j++, k++  
23
24   Iteration 5 :  i = 2, j = 2 and k = 4  
25                  Compare A[2] with B[2]  
26                  here A[2] < B[2] => C[4] = A[2] and i++, k++  
27
28   Iteration 6 :  i = 3 and j = 2 and k = 5  
29                  Compare A[3] with B[2]  
30                  here A[3] < B[2] => C[5] = A[3] and i++, k++  
31
32   Iteration 7: i = 4 and j = 2 and k = 6  
33      As A elements over C[6] = B[2] and j++  
34
35Both A and B elements exhausted and we got the final array C.

Output : {1, 2, 3, 4, 5, 6, 7}

Java Implementation

1import java.util.Arrays;
2public class MergeTwoSortedArrays {
3
4    public int[] merge(int[] A, int[] B) {
5        // initialize m and n to length of arrays A and B
6        int m = A.length;
7        int n = B.length;
8
9        // create result array C of length (m+n)
10        int[] C = new int[m+n] ;
11
12        // initialize i, j and k to 0
13        // Index i is for array A
14        // Index j is for array B
15        // Index k is for result array C
16        int i=0 , j = 0, k = 0;
17
18        //Condition to check any array got exhausted ?
19        while(i < m && j < n){
20
21            // compare A[i] with B[j]
22            if(A[i] < B[j]){
23
24                // As A[i] is smaller, copy A[i] into C[k]
25                C[k] = A[i];
26
27                // as A[i] processed move to next element by incrementing i
28                // as C[k] already filled, move to next index by incrementing k
29                i++; k++;
30            }else{
31
32                // As B[j] is smaller, copy B[j] into C[k]
33                C[k] = B[j];
34
35                // as B[j] processed move to next element by incrementing j
36                // as C[k] already filled, move to next index by incrementing k
37                j++; k++;
38            }
39        }
40
41        // This is the case when array B all elements processed & 
42        // A has still unvisited elements
43        while(i < m) {
44            C[k++] = A[i++];
45        }
46
47        // This is the case when array A all elements processed &
48        // B has still unvisited elements
49        while (j < n) {
50            C[k++] = B[j++];
51        }
52        
53        // return the result array
54        return C;
55    }
56
57    // Driver Code to test the code
58    public static void main(String[] args) {
59        MergeTwoSortedArrays obj = new MergeTwoSortedArrays();
60        int[] A = {1, 3, 5, 6};
61        int[] B = {2, 4, 7};
62        int[] resultArray = obj.merge(A, B);
63        System.out.println(Arrays.toString(resultArray));
64    }
65}

Complexity Analysis

• Time Complexity : O(m+n) where m and n are length of arrays A and B respectively.
• Space Complexity: O(1) as we are not using any extra space.

Approaches Comparison