Merge Two Sorted Arrays

Difficulty: Medium

Asked in: Microsoft, Adobe

Understanding The Problem

Problem Description

You are given two sorted arrays arr1[] and arr2[] of sizes m and n respectively. Write a program to merge them in such a way that the resultant array is sorted too.

Problem Note:

The size of the resultant array should be m+n.
You are expected to solve this question in O(m+n) time.
Your final array should be the first array i.e. array arr1[].

Example 1

Input: arr1[] = [3, 9, 10, 18, 23], arr2[] = [5, 12, 15, 20, 21, 25]
m = 5, n = 6
Output: [3, 5, 9, 10, 12, 15, 18, 20, 21, 23, 25]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 5 + 6 = 11

Example 2

Input: arr1[] = [2, 5, 9], arr2[] = [12, 19, 23], m = 3, n = 3
Output: [2, 5, 9, 12, 19, 23]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 3 + 3 = 6

Example 3

Input: arr1[] = [2, 20], arr2[] = [5, 9, 14, 16, 19], m = 2, n = 5
Output: [2, 5, 9, 14, 16, 19, 20]
Explanation: The resultant array i.e. arr1[] has all the elements of arr1[] and arr2[], sorted in increasing order. The size of resultant array is m + n = 2 + 5 = 7

Solutions

We will be discussing two different solutions to this problem:-

Merge Function of merge sort: Auxiliary array of n+m size storing values as merge function in merge sort.
Two pointers: Compare the two values from the end of ar1 and ar2 and store in ar1 while decrementing pointers accordingly.

You should try to solve the problem here.

1. Merge Function of Merge Sort

The two given array is sorted, so we can directly use the merge function of merge sort. We create an auxiliary array of size m+n and then follow the merge function of the merge sort.

Refer to the below example.

Solution Steps

Create an auxiliary array of size m+ n where m and n are the sizes of ar1 and ar2 respectively.
While traversing through both the arrays: Pick the smaller of current elements of arr1 and arr2, save the smaller value of both the arrays in the auxiliary array, thereby increment the positions accordingly.
Now copy the auxiliary array to arr1 as the final array should be arr1

Pseudo Code

void mergeArrays(int arr1[], int arr2[], int n, int m) { 
    int i = 0, j = 0, k = 0
    int[m+n] arr3
    // Traverse both array 
    while (i < n and j < m) { 
        if (arr1[i] < arr2[j]) {
            arr3[k] = arr1[i]
            i = i + 1 
        }
        else{
            arr3[k] = arr2[j]
            j = j + 1
        }
        k = k + 1
    }
    while (i < n){
        arr3[k] = arr1[i]
        i = i + 1
        k = k + 1
    } 
    while (j < m){
        arr3[k] = arr2[j]
        j = j + 1
        k = k + 1
    } 
    // copy arr3 to arr1
    i = 0
    while(i < (m + n)){
        arr1[i] = arr3[i]
        i = i + 1
    }
    return arr1
}

Complexity Analysis

Time Complexity: O(n+m)

Space Complexity: O(n+m)

Critical Ideas To Think

Why did we create an auxiliary array?
How we are traversing both the array?
On what basis we are storing the value in the auxiliary array from arr1 and arr2?

2. Two Pointers

The problem statement requires the output after merge operation in arr1 . This states that arr1 has enough space to accommodate the elements of arr1 and arr2.

Now, the two given array are already sorted, so we can put two pointers at the end of each array, say i is pointing arr1[n-1] and j is pointing arr2[m-1]. A third pointer k pointing to arr1[n+m-1]. then we start comparing values at the pointers i and j, the larger value will be stored at the pointer k thereby decreasing the pointer with larger value by 1 and decreasing the pointer k by 1. We can continue comparing the values unless i and j reach to 0th index.

Considering the above Example1:

step 1)
                       i                      k 
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , _ , _]
                           j
arr2 = [5, 12, 15, 20, 21, 25]
step 2) arr1[i] < arr2[j] => arr1[k] = arr2[j], j--, k--
                       i                  k 
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , _ , 25]
                        j
arr2 = [5, 12, 15, 20, 21, 25]
step 3) arr1[i] > arr2[j] => arr1[k] = arr1[i], i--, k--
                   i                  k 
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , _ , 23 , 25]
                        j
arr2 = [5, 12, 15, 20, 21, 25]
step 4) arr1[i] < arr2[j] => arr1[k] = arr2[j], j--, k--
                   i              k 
arr1 = [3, 9, 10, 18, 23, _ , _ , _ , 21 , 23 , 25]
                    j
arr2 = [5, 12, 15, 20, 21, 25]
step 5) arr1[i] < arr2[j] => arr1[k] = arr2[j], j--, k--
                   i          k 
arr1 = [3, 9, 10, 18, 23, _ , _ , 20 , 21 , 23 , 25]
                j
arr2 = [5, 12, 15, 20, 21, 25]
.
.
step 10) arr1[i] < arr2[j] => arr1[k] = arr2[j], j--, k--
        i  k 
arr1 = [3, 5, 9, 10, 12, 15 , 18 , 20 , 21 , 23 , 25]
        j
arr2 = [5, 12, 15, 20, 21, 25]

Solution Steps

Create two pointers i, j pointing at arr1[n] and arr2[m]
While i ≥ 0 and j ≥ 0, the pointer with larger value by one and decrease k by 1.
Return arr1

Pseudo Code

void mergeArrays(int arr1[], int arr2[], int n, int m) { 
    int i = n-1
    int j = m-1
    int k = n+m-1
    // Traverse both array 
    while (i >= 0 and j >= 0) { 
        if (arr1[i] > arr2[j]) {
            arr1[k] = arr1[i]
            i = i - 1 
        }
        else{
            arr1[k] = arr2[j]
            j = j - 1
        }
        k = k - 1
    }
    while (i >= 0){
        arr1[k] = arr1[i]
        i = i - 1
        k = k - 1
    } 
    while (j >= 0){
        arr1[k] = arr2[j]
        j = j - 1
        k = k - 1
    } 
    return arr1
}

Complexity Analysis

Time Complexity: O(n+m)

Space Complexity: O(1)

Critical Ideas To Think

Why did we iterate from backward of arr1 and arr2?
How different is this approach compared to the merge function of the merge sort?
Why is the space complexity is O(1)?

AfterAcademy