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:-

  1. Merge Function of merge sort : Auxiliary array of n+m size storing values as merge function in merge sort.
  2. 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)?

Comparison of Different Approaches

Suggested Problems To Solve

  • Merge two sorted linked list.
  • Merge K sorted arrays.
  • Merge two sorted arrays using a heap.
  • Merge two unsorted linked list to get a sorted list.
  • Merge K sorted arrays of different sizes.

Please comment down below if you have a better insight in the above approach.

Happy Coding, Enjoy Algorithms!