Merge the sequences (#9593)

Algorithm Analysis

We can read both sequences into one array and sort it. The task will be solved in time $O (n lo g_{2} n)$ .

Merging will be called the combination of two (or more) ordered sequences into one ordered sequence. Merging can be done using the merge function from STL. Complexity $O (n)$ .

Let's consider the merging process of sequences a and b in more detail. Declare three variables - pointers p, q, i and set them:

p = 0, at the beginning of the first array a;
q = 0, at the beginning of the first array b;
i = 0, at the beginning of the resulting array res.

At each step (iteration), we compare the values of a[p] and b[q]. Assign the lesser of these values to res[i], after which we increase by 1 the pointer i and the pointer to the smaller element (p or q). For example, after several steps, we can get the following state of the arrays:

When the pointer in one of the arrays reaches the end, the remaining part of the other array should be copied into the resulting array.

Algorithm Implementation

Declare working arrays.

vector<int> a, b, res;

Read two input sequences.

scanf("%d", &n);
a.resize(n);
for (i = 0; i < n; i++) scanf("%d", &a[i]);
scanf("%d", &m);
b.resize(m);
for (i = 0; i < m; i++) scanf("%d", &b[i]);

Set the size of the resulting sequence - it equals $n + m$ .

res.resize(n + m);

Initialize pointers.

p = q = 0;

As long as neither of the pointers has reached the end of the array, assign res[i] = min(a[p], b[q]) and advance the corresponding pointers by one.

for (i = 0; p < n && q < m; i++)
{
    if (a[p] <= b[q]) res[i] = a[p], p++;
    else res[i] = b[q], q++;
}

One of the pointers reached the end of the array. Copy the remainder of the second array into the resulting one. If at this moment p = n, then only the second while will work. If at this moment q = m, then only the first while will work.

while (p < n) res[i++] = a[p++];
while (q < m) res[i++] = b[q++];

Print the resulting sequence.

for (i = 0; i < n + m; i++) printf("%d ", res[i]);
printf("\n");

Algorithm Implementation - Sorting

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int i, n, m;
vector<int> a;

int main(void)
{
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    a.resize(n + m);
    for (i = 0; i < m; i++) scanf("%d", &a[n + i]);
    sort(a.begin(), a.end());
    for (i = 0; i < n + m; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Algorithm Implementation - STL merge

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int i, n, m;
vector<int> a, b, res;

int main(void)
{
    scanf("%d", &n);
    a.resize(n);
    for (i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    b.resize(m);
    for (i = 0; i < m; i++) scanf("%d", &b[i]);
    res.resize(n + m);
    merge(a.begin(), a.end(), b.begin(), b.end(), res.begin());
    for (i = 0; i < n + m; i++) printf("%d ", res[i]);
    printf("\n");
    return 0;
}

Java Implementation

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int n = con.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++)
            a[i] = con.nextInt();
        
        int m = con.nextInt();
        int b[] = new int[m];
        for(int i = 0; i < m; i++)
            b[i] = con.nextInt();
        
        int res[] = new int[n + m];
        int p = 0, q = 0, i;
        for (i = 0; p < n && q < m; i++)
        {
            if (a[p] <= b[q])
            {
                res[i] = a[p];
                p++;
            }
            else
            {
                res[i] = b[q];
                q++;
            }
        }
        
        while (p < n) res[i++] = a[p++];
        while (q < m) res[i++] = b[q++];
        
        for (i = 0; i < n + m; i++)
            System.out.print(res[i] + " ");
        System.out.println();
        con.close();
    }
}