Merge two sorted arrays Solutions-Using Merge of MergeSort

Making Use of Merge of MergeSort
Merge function of Merge sort is supposed to be used here.

• Create a n1 + n2 sized array arr3[].
• Go simultaneously over arr1[] and arr2[].
• Copy a smaller element from arr1[] and arr2[], then advance in arr3[] and the array whose element is chosen from arr1[] and arr2[].
• Copy any remaining components from arr1[ or arr2[] also in arr3[].
• Here is a graphic showing the above method:

Consider two sorted arrays, Array 1 and Array 2, together with an empty array, Array 3. Here “i” pointer refers towards 0th index of Array1, similarly “j” and “k” pointer points towards 0th index of Array2 and Array3 for comparisons.

C++

#include <iostream>
#include <vector>
using namespace std;

// Merge ar1[0..n1-1] and ar2[0..n2-1] into ar3
void mergeArrays(vector<int>& ar1, vector<int>& ar2, 
                               vector<int>& ar3) {
    int i = 0, j = 0, k = 0;
    int n1 = ar1.size();
    int n2 = ar2.size();

    while (i < n1 && j < n2) {
      
        // Pick smaller of the two current
        // elements and move ahead in the
        // array of the picked element
        if (ar1[i] < ar2[j])
            ar3[k++] = ar1[i++];
        else
            ar3[k++] = ar2[j++];
    }

    // if there are remaining elements of
    // the first array, move them
    while (i < n1)
        ar3[k++] = ar1[i++];

    // Else if there are remaining elements of
    // the second array, move them
    while (j < n2)
        ar3[k++] = ar2[j++];
}

// Driver code
int main() {
    vector<int> ar1 = {1, 3, 5, 7};
    vector<int> ar2 = {2, 4, 6, 8};
    vector<int> ar3(ar1.size() + ar2.size());

    mergeArrays(ar1, ar2, ar3);
  
    for (int i = 0; i < ar3.size(); i++)
        cout << ar3[i] << " ";

    return 0;
}

C

#include <stdio.h>

// Merge ar1[0..n1-1] and ar2[0..n2-1] into ar3
void mergeArrays(int* ar1, int n1, int* ar2, int n2, int* ar3) {
    int i = 0, j = 0, k = 0;

    while (i < n1 && j < n2) {
      
        // Pick smaller of the two current elements and move ahead in the array of the picked element
        if (ar1[i] < ar2[j])
            ar3[k++] = ar1[i++];
        else
            ar3[k++] = ar2[j++];
    }

    // if there are remaining elements of the first array, move them
    while (i < n1)
        ar3[k++] = ar1[i++];

    // Else if there are remaining elements of the second array, move them
    while (j < n2)
        ar3[k++] = ar2[j++];
}

// Driver code
int main() {
    int ar1[] = {1, 3, 5, 7};
    int ar2[] = {2, 4, 6, 8};
    int n1 = sizeof(ar1) / sizeof(ar1[0]);
    int n2 = sizeof(ar2) / sizeof(ar2[0]);
    int ar3[n1 + n2];

    mergeArrays(ar1, n1, ar2, n2, ar3);

    for (int i = 0; i < n1 + n2; i++)
        printf("%d ", ar3[i]);

    return 0;
}

Java

import java.util.*;

public class GfG {

    // Merge ar1[0..n1-1] and ar2[0..n2-1] into ar3
    public static void mergeArrays(int[] ar1, int[] ar2, int[] ar3) {
        int i = 0, j = 0, k = 0;
        int n1 = ar1.length;
        int n2 = ar2.length;

        while (i < n1 && j < n2) {
          
            // Pick smaller of the two current elements and move ahead in the array of the picked element
            if (ar1[i] < ar2[j])
                ar3[k++] = ar1[i++];
            else
                ar3[k++] = ar2[j++];
        }

        // if there are remaining elements of the first array, move them
        while (i < n1)
            ar3[k++] = ar1[i++];

        // Else if there are remaining elements of the second array, move them
        while (j < n2)
            ar3[k++] = ar2[j++];
    }

    // Driver code
    public static void main(String[] args) {
        int[] ar1 = {1, 3, 5, 7};
        int[] ar2 = {2, 4, 6, 8};
        int[] ar3 = new int[ar1.length + ar2.length];

        mergeArrays(ar1, ar2, ar3);

        for (int value : ar3)
            System.out.print(value + " ");
    }
}

Python

# Merge ar1[0..n1-1] and ar2[0..n2-1] into ar3
def merge_arrays(ar1, ar2):
    i = 0
    j = 0
    k = 0
    n1 = len(ar1)
    n2 = len(ar2)
    ar3 = []

    while i < n1 and j < n2:
      
        # Pick smaller of the two current elements and move ahead in the array of the picked element
        if ar1[i] < ar2[j]:
            ar3.append(ar1[i])
            i += 1
        else:
            ar3.append(ar2[j])
            j += 1

    # if there are remaining elements of the first array, move them
    while i < n1:
        ar3.append(ar1[i])
        i += 1

    # Else if there are remaining elements of the second array, move them
    while j < n2:
        ar3.append(ar2[j])
        j += 1

    return ar3

# Driver code
ar1 = [1, 3, 5, 7]
ar2 = [2, 4, 6, 8]
ar3 = merge_arrays(ar1, ar2)

print(" ".join(map(str, ar3)))

JavaScript

// Merge ar1[0..n1-1] and ar2[0..n2-1] into ar3
function mergeArrays(ar1, ar2) {
    let i = 0, j = 0, k = 0;
    const n1 = ar1.length;
    const n2 = ar2.length;
    const ar3 = [];

    while (i < n1 && j < n2) {
    
        // Pick smaller of the two current elements and move ahead in the array of the picked element
        if (ar1[i] < ar2[j])
            ar3[k++] = ar1[i++];
        else
            ar3[k++] = ar2[j++];
    }

    // if there are remaining elements of the first array, move them
    while (i < n1)
        ar3[k++] = ar1[i++];

    // Else if there are remaining elements of the second array, move them
    while (j < n2)
        ar3[k++] = ar2[j++];

    return ar3;
}

// Driver code
const ar1 = [1, 3, 5, 7];
const ar2 = [2, 4, 6, 8];
const ar3 = mergeArrays(ar1, ar2);

console.log(ar3.join(" "));

Output

1 2 3 4 5 6 7 8 

Time Complexity : O(n1 + n2) 
Auxiliary Space : O(n1 + n2)