Merge Two Sorted Arrays

Merge Two Sorted Arrays
Merge Two Sorted Arrays

Introduction

Arrays are the most basic and essential data structures. It is critical to be familiar with the well-known interview problems based on arrays. You should consider checking out CodeStudio for such amazing problems.

In this blog, we will see one of the frequently asked interview problems, i.e., Merge Two Sorted Arrays. The problem statement goes like this:

You are provided two non-decreasing sorted arrays, ‘ARR1′ and ‘ARR2.’ Your goal is to merge these two arrays so that the initial sorted elements go into ‘ARR1′ and the rest go into ‘ARR2.’

For example:

Given ARR1[ ] = {1, 5, 7, 19, 34} and ARR2[ ] = {2, 4, 8, 8, 12, 17, 19}.

We can see that both of these two arrays are sorted in non-decreasing order. So after merging, we will have:

ARR1[ ] = {1, 2, 4, 5, 7} and ARR2[ ] = {8, 8, 12, 17, 19, 19, 34}.

We can solve this problem in several different ways. Let us first see how we can solve this by using an auxiliary space.

Using Auxiliary Space

Approach 1

The idea is based on the approach of combining the two arrays and sorting them

Algorithm:

blog banner 1
  1. Suppose the size of ‘ARR1’ is ‘M’ and the size of ‘ARR2’ is ‘N’. So, create an array, ‘ARR3’ of size ‘M + N’. 
  2. Copy the elements from ‘ARR1’ to ‘ARR3’.
  3. Copy the elements from ‘ARR2’ to ‘ARR3’.
  4. Sort the array, ‘ARR3’.
  5. Copy the first ‘M’ elements from ‘ARR3’ to ‘ARR1’ and copy the remaining ‘N’ elements from ‘ARR3’ to ‘ARR2’.

Let us now see the implementation of the above algorithm.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();
   
    // Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
    vector<int> arr3(m + n);
   
    // Copying elements from 'ARR1' to 'ARR3'.
    for (int i = 0; i < m; i++) {
        arr3[i] = arr1[i];
    }
   
    // Copying elements from 'ARR2' to 'ARR3'.
    for (int i = 0; i < n; i++) {
        arr3[i + m] = arr2[i];
    }
   
    // Sorting 'ARR3'.
    sort(arr3.begin(), arr3.end());
   
    // Putting elements back into 'ARR1' from 'ARR3'.
    for (int i = 0; i < m; i++) {
        arr1[i] = arr3[i];
    }
   
    // Putting elements back into 'ARR2' from 'ARR3'.
    for (int i = m; i < m + n; i++) {
        arr2[i - m] = arr3[i];
    }
}

int main() {
    int m, n;
   
    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }
   
    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }
   
    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);
   
    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }

    cout << endl;
   
    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }
   
    return 0;
}

Input

5
1 5 7 19 34
7
2 4 8 8 12 17 19

Output

1 2 4 5 7 
8 8 12 17 19 19 34

Time Complexity

O((M + N) * log(M + N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.

Copying elements from ‘ARR1’ to ‘ARR3’ takes O(M) time.

Copying elements from ‘ARR2’ to ‘ARR3’ takes O(N) time.

Sorting of ‘ARR3’ takes O((M + N) * log(M + N)) time.

Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.

Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.

So, the overall time complexity is O(M) + O(N) + O((M + N) * log(M + N)) + O(M) + O(N) = O((M + N) * log(M + N)).

Space Complexity

O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.

It is because we have used an additional array, ‘ARR3’ of size ‘M + N’. Hence, the overall space complexity is O(M + N).

Approach 2

Since arrays are already sorted, we can use the merge function of merge sort to optimise the time complexity of Approach 1.

Algorithm:

  1. Suppose the size of ‘ARR1’ is ‘M’ and the size of ‘ARR2’ is ‘N’. So, create an array, ‘ARR3’ of size ‘M + N’. 
  2. Take three variables: ‘i’, ‘j’ and ‘k’. Initialise all of them by zero. These variables, ‘i’, ‘j’ and ‘k’ will indicate the current index of ‘ARR1’, ‘ARR2’ and ‘ARR3’, respectively.
  3. Run a while loop until we reach the end of either ‘ARR1’ or ‘ARR2’.
    1. In every iteration, pick the smaller element out of ‘ARR1[ i ]’ and ‘ARR2[ j ]’, and place it in the ‘ARR3[ k ]’.
    2. Increment the variable ‘k’ and either ‘i’ or ‘j’, depending on the element picked.
  4. When we run out of elements in either ‘ARR1’ or ‘ARR2’, pick up the remaining elements and put in ‘ARR3’.
  5. Copy the first ‘M’ elements from ‘ARR3’ to ‘ARR1’ and copy the remaining ‘N’ elements from ‘ARR3’ to ‘ARR2’.

The implementation of the above algorithm is shown below:

#include <iostream>
#include <vector>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();
   
    // Creating array, 'ARR3' to store elements of 'ARR1' and 'ARR2'.
    vector<int> arr3(m + n);
   
    /*
        The variables, 'i', 'j' and 'k' indicates the current index in arrays, 'ARR1', 'ARR2' and 'ARR3', respectively.
    */
    int i = 0, j = 0, k = 0;
   
    // Merging arrays, 'ARR1' and 'ARR2' in 'ARR3'.
    while (i < m && j < n) {
        if (arr1[i] < arr2[j]) {
            arr3[k] = arr1[i];
            i++;
        }
        else {
            arr3[k] = arr2[j];
            j++;
        }
        k++;
    }
   
    // Copying remaining elements of 'ARR1' in 'ARR3'.
    while (i < m) {
        arr3[k] = arr1[i];
        k++, i++;
    }
   
    // Copying remaining elements of 'ARR2' in 'ARR3'.
    while (j < n) {
        arr3[k] = arr2[j];
        k++, j++;
    }
   
    // Putting elements back into 'ARR1' from 'ARR3'.
    for (int i = 0; i < m; i++) {
        arr1[i] = arr3[i];
    }
   
    // Putting elements back into 'ARR2' from 'ARR3'.
    for (int i = m; i < m + n; i++) {
        arr2[i - m] = arr3[i];
    }
}

int main() {
    int m, n;
   
    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }
   
    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }
   
    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);
   
    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }
   
    cout << endl;
   
    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }
   
    return 0;
}

Input

5
-1 0 7 18 34
7
0 4 8 9 12 12 18

Output

-1 0 0 4 7 
8 9 12 12 18 18 34

Time Complexity

O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.

Copying elements of ‘ARR1’ and ‘ARR2’ to ‘ARR3’ takes O(M + N) time.

Putting elements back into ‘ARR1’ from ‘ARR3’ takes O(M) time.

Putting elements back into ‘ARR2’ from ‘ARR3’ takes O(N) time.

So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).

Space Complexity

O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of array ‘ARR2’.

Again, the space complexity is O(M + N) as we have used an additional array, ‘ARR3’ of size ‘M + N’.

Without Using Auxiliary Space

Approach 1

In this approach, we will compare every element of the array, ‘ARR1’, with the first element of the array, ‘ARR2’. If the element of ‘ARR1’ is greater than the first element of ‘ARR2’, we will swap those elements and sort the array, ‘ARR2’, so that the smallest element is always at the index ‘0’. In this way, we can easily merge the arrays without any extra space.

Algorithm:

  1. Run a loop to traverse the elements of the array, ‘ARR1’.
    1. For every element, ‘element’ in ‘ARR1’. Check whether ‘element’ > ‘ARR2[ 0 ]’.
      1. If yes, swap ‘element’ with ‘ARR2[ 0 ]’ and sort the array, ‘ARR2’.

Let us now see the implementation of the above algorithm.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();
   
    // Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
    for (int i = 0; i < m; i++) {
       
        // If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
        if (arr1[i] > arr2[0]) {
            swap(arr1[i], arr2[0]);
            sort(arr2.begin(), arr2.end());
        }
    }
}

int main() {
    int m, n;
   
    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }
   
    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }
   
    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);
   
    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }
   
    cout << endl;
   
    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }
   
    return 0;
}

Input

7
1 1 2 7 90 899 1000
2
0 0

Output

0 0 1 1 2 7 90 
899 1000

Time Complexity

O(M * N * log(N)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.

It is because the for loop runs ‘M’ times, and in each iteration, we are sorting the array, ‘ARR2’, depending on the if condition. In the worst case, when every element of ‘ARR1’ is greater than ‘ARR2’, sorting will be performed in every iteration, taking O(N * log (N)) time.

So, the overall time complexity is O(M) * O(N * log(N)) = O(M * N * log(N)).

Space Complexity

O(1).

As no auxiliary space has been used here.

Approach 2

The only goal in Approach 1 is to place the swapped element in ‘ARR2′ at the correct position after swapping the elements. In such a situation, sorting the entire array is unnecessary. We can use the insertion sort algorithm to shift the elements and place the swapped element at the correct position.

Algorithm:

  1. Run a loop to traverse the elements of the array, ‘ARR1’.
    1. For every element, ‘element’ in ‘ARR1’. Check whether ‘element’ > ‘ARR2[ 0 ]’.
      1. If yes, swap ‘element’ with ‘ARR2[ 0 ]’.
      2. To sort the array, ‘ARR2’, store the first element in a variable, ‘K’ and then run a loop to left shift all the elements smaller than ‘K’. In the end, put the element ‘K’ at the correct position in the array.

The implementation of the above algorithms is provided below.

#include <iostream>
#include <vector>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();
   
    // Traversing 'ARR1' and comparing its every element with 'ARR2[0]'.
    for (int i = 0; i < m; i++) {
       
        // If 'ARR1[i] > ARR2[0]', swap them and sort 'ARR2'.
        if (arr1[i] > arr2[0]) {
            swap(arr1[i], arr2[0]);
           
            int k = arr2[0], j;
           
            // Shifting elements of the array, 'ARR2' to place 'ARR2[0]' at correct position.
            for (j = 1; j < n; j++) {
                if (arr2[j] < k) {
                    arr2[j-1] = arr2[j];
                }
                else {
                    break;
                }
            }
            arr2[j - 1] = k;
        }
    }
}

int main() {
    int m, n;
   
    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }
   
    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }
   
    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);
   
    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }
   
    cout << endl;
   
    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }
   
    return 0;
}

Input

7
1 1 2 7 90 899 1000
2
0 0

Output

0 0 1 1 2 7 90 
899 1000

Time Complexity

O(M * N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.

It is because the for loop runs ‘M’ times, and in each iteration, we are shifting the elements of the array, ‘ARR2’, depending on the if condition. In the worst case, when all the elements of ‘ARR1’ will be greater than all the elements of ‘ARR2’, shifting will be performed in every iteration for all the elements of ‘ARR2’, which will take O(N) time.

So, the overall time complexity is O(M) * O(N) = O(M * N).

Space Complexity

O(1).

As no auxiliary space has been used here.

Approach 3

Suppose there are ‘M’ elements in ‘ARR1’ and ‘N’ elements in ‘ARR2’. We will modify the arrays, ‘ARR1’ and ‘ARR2’ so that out of these ‘M + N’ elements, the first ‘M’ smaller elements are kept in ‘ARR1’ and the next ‘N’ elements are kept in ‘ARR2’. We will not maintain the sorted order while segregating the elements.

When elements are successfully segregated, we can sort both of these arrays to obtain the desired result.

Algorithm:

  1. Store size of ‘ARR1’ and ‘ARR2’ in variables ‘M’ and ‘N’, respectively.
  2. Take two variables, ‘i’ and ‘j’ and initialise them with zero.
  3. Run a while loop till i < M and j < N.
    1. If ARR1[ i ] < ARR2[ j ] that shows the ‘i’th element in ‘ARR1’ is smaller than ‘j’th element in ‘ARR2’. Since we have to keep first ‘M’ smaller elements in ‘ARR1’. We will simply increment the variable ‘i’.
    2. Else, we will swap the element ‘ARR2[ j ]’ with the element ‘ARR1[ M – 1 ]’. Then, decrement ‘M’ and increment ‘j’.
  4. At this point, we will be having the first ‘M’ smaller elements in ‘ARR1’ and the next ‘N’ elements in ‘ARR2’. So now sort the arrays, ‘ARR1’ and ‘ARR2’.

The implementation of the above algorithm is provided below:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();
   
    int i = 0, j = 0;
 
  // Segregating elements.
    while (i < m && j < n) {
        if (arr1[i] < arr2[j])
            i++;
        else {
            swap(arr1[m - 1], arr2[j]);
            m--, j++;
        }
    }
   
    // Sorting array, 'ARR1'.
    sort(arr1.begin(), arr1.end());
   
    // Sorting array, 'ARR2'.
    sort(arr2.begin(), arr2.end());
}

int main() {
    int m, n;
   
    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }
   
    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }
   
    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);
   
    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }
   
    cout << endl;
   
    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }
   
    return 0;
}

Input

4
-3 -1 5 8
7
-2 -1 0 1 3 5 7

Output

-3 -2 -1 -1 
0 1 3 5 5 7 8

Time Complexity

O(M * log(M) + N * log(M)), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.

Segregation of elements of takes O(max(M, N)) time.

Sorting array, ‘ARR1’ takes O(M * log(M)) time.

Sorting array, ‘ARR2’ takes O(N * log(N)) time.

So, the overall time complexity is O(max(M, N)) + O(M * log(M)) + O(N * log(N)) = O(M * log(M) + N * log(M)).

Space Complexity

O(1).

As no auxiliary space has been used here.

Approach 4 (For Non-Negative Integers)

In this approach, we will again use the merge function of the merge sort to merge the arrays, ‘ARR1’ and ‘ARR2’. In the usual merge function, we use an auxiliary array to maintain the merged elements in a sorted manner. To achieve the same without any extra space, we will store the new and old values in the same location by using division and modulus operators. Let us see how.

Suppose we have an integer variable, ‘VAR’, containing an integer ‘X’. Now, we also want to store an integer, ‘Y’ in ‘VAR’ so, if we change VAR = X to VAR = X + Y * N, where ‘N’ is an integer greater than both ‘X’ and ‘Y’.

In that case, VAR / N = Y and VAR % N = X.

So, the old value ‘X’ and the new value ‘Y’ are now contained by the same variable ‘VAR’.

The implementation of the above approach is provided below:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Function to merge two sorted arrays.
void mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int m = arr1.size(), n = arr2.size();

    // 'MAXN' will store the value greater than all the elements of 'ARR1' and 'ARR2'.
    int maxN = max(*max_element(arr1.begin(), arr1.end()), *max_element(arr2.begin(), arr2.end()));

    // Incrementing 'MAXN' by 1 to avoid collision in modulo operation.
    maxN++;

    int i = 0, j = 0, k = 0;

    while (i < m && j < n && k < (m + n)) {

        // Extracting the old values.
        int element1 = arr1[i] % maxN;
        int element2 = arr2[j] % maxN;

        if (element1 <= element2) {

            // Updating element with new value.
            if (k < m) {
                arr1[k] += (element1 * maxN);
            }
            else {
                arr2[k - m] += (element1 * maxN);
            }
            i++, k++;
        }
        else {

            // Updating element with new value.
            if (k < m) {
                arr1[k] += (element2 * maxN);
            }
            else {
                arr2[k - m] += (element2 * maxN);
            }
            j++, k++;
        }
    }

    // Processing remaining elements of 'ARR1'.
    while (i < m) {
        int element = arr1[i] % maxN;

        if (k < m) {
            arr1[k] += (element * maxN);
        }
        else {
            arr2[k - m] += (element * maxN);
        }

        i++, k++;
    }

    // Processing remaining elements of 'ARR2'.
    while (j < n) {
        int element = arr2[j] % maxN;

        if (k < m) {
            arr1[k] += (element * maxN);
        }
        else {
            arr2[k - m] += (element * maxN);
        }

        j++, k++;
    }

    // Updating 'ARR1' elements with new values.
    for (int i = 0; i < m; i++) {
        arr1[i] = arr1[i] / maxN;
    }

    // Updating 'ARR2' elements with new values.
    for (int i = 0; i < n; i++) {
        arr2[i] = arr2[i] / maxN;
    }
}

int main() {
    int m, n;

    // Taking input for 'ARR1'.
    cin >> m;
    vector<int> arr1(m);
    for (int &element : arr1) {
        cin >> element;
    }

    // Taking input for 'ARR2'.
    cin >> n;
    vector<int> arr2(n);
    for (int &element : arr2) {
        cin >> element;
    }

    // Calling function to merge the arrays, 'ARR1' and 'ARR2'.
    mergeSortedArrays(arr1, arr2);

    // Printing elements of 'ARR1'.
    for (int &element : arr1) {
        cout << element << " ";
    }

    cout << endl;

    // Printing elements of 'ARR2'.
    for (int &element : arr2) {
        cout << element << " ";
    }

    return 0

Input

4
1 3 5 8
7
0 1 3 5 7 8 11

Output

0 1 1 3 
3 5 5 7 8 8 11

Time Complexity

O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array ‘ARR2’.

Merging elements of ‘ARR1’ and ‘ARR2’ in ‘ARR3’ takes O(M + N) time.

Updating ‘ARR1’ elements with new values takes O(M) time.

Updating ‘ARR2’ elements with new values takes O(N) time.

So, the overall time complexity is O(M + N) + O(M) + O(N) = O(M + N).

Space Complexity

O(1).

As no auxiliary space has been used here.

Frequently Asked Questions

How do I combine two arrays?

Suppose you have two arrays, ‘ARR1’ and ‘ARR2’ of size ‘M’ and ‘N’, respectively. To combine them, we need to create another array, ‘ARR3’ of size ‘M + N’ to combine them. After that, we will copy ‘M’ elements from ‘ARR1’ into ‘ARR3’ and ‘N’ elements from ‘ARR2’ into ‘ARR3’. In this way, the array, ‘ARR3’, will contain the combination of arrays, ‘ARR1’ and ‘ARR2’.

How do I merge two sorted arrays without duplicates?

We’ve covered six approaches for merging two sorted arrays in this blog. All of these approaches work for sorted arrays with no duplicates as well. As a result, depending on whether you wish to use extra space or not, you can merge the arrays using any approach.

What is the best time complexity to merge two sorted arrays?

The best-case scenario of merging two sorted arrays, ‘ARR1’ and ‘ARR2’ will be when all the elements of the first array, ‘ARR1’ are smaller than the second array, ‘ARR2’ or vice versa. In that scenario, all we have to do is figure out whether ‘ARR1′ comes before ‘ARR2′ or vice versa. If the last element in the first array is smaller than the first element in the second array, the correct order can be determined with just one comparison. Hence, the time complexity is O(1).

However, if it is needed to merge these two arrays in a third array, ‘ARR3’, then we need to copy the elements from both the arrays to ‘ARR3’. Therefore, the time complexity will become O(M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array, ‘ARR2’.

What is the minimum time complexity to merge two given sorted arrays considering no extra auxiliary space?

In this blog, we have discussed four approaches to merge two sorted arrays without extra space. Out of them, Approach 4 has the minimum time complexity, O (M + N), where ‘M’ is the size of the array, ‘ARR1’ and ‘N’ is the size of the array, ‘ARR2’.

Can you do merge sort in place?

Yes, it is possible to perform an in-place merge sort.

How do you add two arrays in Python?

Suppose you have two arrays, ARR1[ ] = {1, 4, 8} and ARR2[ ] = {-1, 5, 9}. There is a naive method that is not language-dependent to add these arrays, i.e., to use a loop to add them element by element. The implementation for the same is provided below.

arr1 = [1, 4, 8]
arr2 = [-1, 5, 9]
arr3 = [None] * (len(arr1))
for i in range(len(arr1)):
arr3[i] = arr1[i] + arr2[i]
print (arr3)

Output
[0, 9, 17]

Another way is to use the Numpy library of python. It provides us with an add() method to add two arrays. Let us see its implementation.

import numpy as np
arr1 = np.array([1, 4, 8])
arr2 = np.array([-1, 5, 9])
arr3 = np.add(arr1, arr2)
print (arr3)

Output
[0, 9, 17]

How do you sort an array?

There are several sorting algorithms that you can use to sort an array. A few popular sorting algorithms are Insertion Sort, Bubble Sort, Selection Sort, Quick Sort, and Merge Sort. We have gone over these algorithms in detail here. Now, depending on your space and time requirements, you can choose the algorithm that suits you best.

Also, there is an inbuilt sort() function in every programming language which you can directly use to sort an array.

Key Takeaways

With this discussion, this blog attempted to break down the famous interview problem, merge two sorted arrays. We discussed different approaches and their time and space complexity. Now, next time someone asks you to merge two sorted arrays without extra space, you are going to shine!

Consider checking out the Guided Path of Data Structures and Algorithms to learn more useful concepts. Also, head over right now to CodeStudio to practice similar problems and crack your interviews like a Ninja!

We hope you found this blog useful. Feel free to let us know your thoughts in the comments section.

By: Vivek Kumar Mehta