Merge two sorted arrays-Using BST

Using Self Balancing BST:

1. Insert elements of both arrays in a tree map as keys.
2. Print the keys of the map.

C++

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

void mergeArrays(vector<int>& ar1, vector<int>& ar2, 
                                   vector<int>& ar3) {
    map<int, int> mp;

    // Inserting values from both vectors into the map
    for (int i = 0; i < ar1.size(); i++) mp[ar1[i]]++;
    for (int i = 0; i < ar2.size(); i++) mp[ar2[i]]++;

    // Traverse through map and insert elements
    // into ar3.
    for (auto& x : mp) {
        for (int i = 0; i < x.second; i++) {
            ar3.push_back(x.first);
        }
    }
}

// Driver Code
int main() { 
    vector<int> ar1 = {1, 3, 5, 7};
    vector<int> ar2 = {2, 4, 6, 8};
    vector<int> ar3;
    mergeArrays(ar1, ar2, ar3);
    for (int i = 0; i < ar3.size(); i++) {
        cout << ar3[i] << " ";
    }
    return 0;
}

C

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

// Function to compare two integers for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// Function to merge two arrays and sort the result
void mergeArrays(int* ar1, int n1, int* ar2, int n2, int* ar3, int* n3) {
    int mp[1000] = {0}; // Assuming the values are in range 0-999
    int i;

    // Inserting values from both arrays into the map
    for (i = 0; i < n1; i++) mp[ar1[i]]++;
    for (i = 0; i < n2; i++) mp[ar2[i]]++;

    // Traverse through map and insert elements into ar3
    *n3 = 0;
    for (i = 0; i < 1000; i++) {
        while (mp[i]--) {
            ar3[(*n3)++] = i;
        }
    }

    // Sort ar3
    qsort(ar3, *n3, sizeof(int), compare);
}

// Driver code
int main() {
    int ar1[] = {1, 3, 5, 7};
    int ar2[] = {2, 4, 6, 8};
    int ar3[100]; // Large enough array to hold all elements
    int n3;

    mergeArrays(ar1, sizeof(ar1)/sizeof(ar1[0]), ar2, sizeof(ar2)/sizeof(ar2[0]), ar3, &n3);

    for (int i = 0; i < n3; i++) {
        printf("%d ", ar3[i]);
    }

    return 0;
}

Java

import java.util.*;

public class GfG {

    // Function to merge two arrays and sort the result
    public static void mergeArrays(int[] ar1, int[] ar2, ArrayList<Integer> ar3) {
        Map<Integer, Integer> mp = new TreeMap<>();

        // Inserting values from both arrays into the map
        for (int i : ar1) mp.put(i, mp.getOrDefault(i, 0) + 1);
        for (int i : ar2) mp.put(i, mp.getOrDefault(i, 0) + 1);

        // Traverse through map and insert elements into ar3
        for (Map.Entry<Integer, Integer> entry : mp.entrySet()) {
            for (int i = 0; i < entry.getValue(); i++) {
                ar3.add(entry.getKey());
            }
        }

        // Sort the entire ar3
        Collections.sort(ar3);
    }

    // Driver code
    public static void main(String[] args) {
        int[] ar1 = {1, 3, 5, 7};
        int[] ar2 = {2, 4, 6, 8};
        ArrayList<Integer> ar3 = new ArrayList<>();
        mergeArrays(ar1, ar2, ar3);

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

Python

from collections import Counter

# Function to merge two arrays and sort the result
def merge_arrays(ar1, ar2):
    mp = Counter(ar1) + Counter(ar2)
    
    # Traverse through map and insert elements into ar3
    ar3 = []
    for key, count in mp.items():
        ar3.extend([key] * count)

    # Sort the entire ar3
    ar3.sort()
    return ar3

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

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

Output

1 2 3 4 5 6 7 8 

Time Complexity: O((n1 + n2)* Log(n1 + n2))
Auxiliary Space: O(n1 + n2) for the tree map.