Merge two sorted arrays Solutions

/ DSA / By
Spread the love
Skylinewebz

Merging two sorted arrays is the challenge here in a sorted way.

Examples: 

Input: arr1[] = { 1, 3, 4, 5}, arr2[] = {2, 4, 6, 8} 
Output: arr3[] = {1, 2, 3, 4, 4, 5, 6, 8}

Input: arr1[] = { 5, 8, 9}, arr2[] = {4, 7, 8} 
Output: arr3[] = {4, 5, 7, 8, 8, 9} 

Table of Content

The naïve approach to accomplish the same is physical force. Combine all of arr 1’s and arr 2’s components in arr 3. Sort the arr3 then just once more.

Table of Contents

C++

#include <bits/stdc++.h>
using namespace std;

void mergeArrays(vector<int>& arr1, vector<int>& arr2, 
                                    vector<int>& arr3) {
    int n1 = arr1.size();
    int n2 = arr2.size();
    int i = 0, j = 0, k = 0;

    // Traverse arr1 and insert its elements into arr3
    while (i < n1) {
        arr3[k++] = arr1[i++];
    }

    // Traverse arr2 and insert its elements into arr3
    while (j < n2) {
        arr3[k++] = arr2[j++];
    }

    // Sort the entire arr3
    sort(arr3.begin(), arr3.end());
}

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

    mergeArrays(arr1, arr2, arr3);

    for (int i = 0; i < arr3.size(); i++)
        cout << arr3[i] << " ";

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>

// Function to merge two arrays and sort the result
void mergeArrays(int* arr1, int n1, int* arr2, int n2, int* arr3) {
    int i = 0, j = 0, k = 0;

    // Traverse arr1 and insert its elements into arr3
    while (i < n1) {
        arr3[k++] = arr1[i++];
    }

    // Traverse arr2 and insert its elements into arr3
    while (j < n2) {
        arr3[k++] = arr2[j++];
    }

    // Sort the entire arr3
    qsort(arr3, n1 + n2, sizeof(int), [](const void* a, const void* b) {
        return (*(int*)a - *(int*)b);
    });
}

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

    mergeArrays(arr1, n1, arr2, n2, arr3);

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

    return 0;
}

Java

import java.util.Arrays;

public class GfG {

    // Function to merge two arrays and sort the result
    public static void mergeArrays(int[] arr1, int[] arr2, int[] arr3) {
        int n1 = arr1.length;
        int n2 = arr2.length;
        int i = 0, j = 0, k = 0;

        // Traverse arr1 and insert its elements into arr3
        while (i < n1) {
            arr3[k++] = arr1[i++];
        }

        // Traverse arr2 and insert its elements into arr3
        while (j < n2) {
            arr3[k++] = arr2[j++];
        }

        // Sort the entire arr3
        Arrays.sort(arr3);
    }

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

        mergeArrays(arr1, arr2, arr3);

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

Python

# Function to merge two arrays and sort the result
def merge_arrays(arr1, arr2):
    arr3 = arr1 + arr2
    arr3.sort()
    return arr3

# Driver code
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
arr3 = merge_arrays(arr1, arr2)

for value in arr3:
    print(value, end=" ")

Output

1 2 3 4 5 6 7 8

Time Complexity : O((n1 + n2) log(n1 + n2)) , the whole size of arr3 is m+n
Auxiliary Space: O(1)