5660: Merging Arrays
[Creator : ]
Description
For educational purposes, in the problems of this block, the time limit is large enough for the solution to pass in $O(nlogn)$ time, but try to write the solution in linear time, which we discussed in the lecture.
You are given two arrays, sorted in non-decreasing order. Merge them into one sorted array.
You are given two arrays, sorted in non-decreasing order. Merge them into one sorted array.
Input
The first line contains integers $n,\ m,\ (1≤n,\ m≤10^5)$ the sizes of the arrays.
The second line contains $n$ integers $a_i$, elements of the first array.
The third line contains $m$ integers $b_i$, elements of the second array ($−10^9≤a_i,\ b_i≤10^9$).
The second line contains $n$ integers $a_i$, elements of the first array.
The third line contains $m$ integers $b_i$, elements of the second array ($−10^9≤a_i,\ b_i≤10^9$).
Output
Print $n+m$ integers, the merged array.
Sample 1 Input
6 7
1 6 9 13 18 18
2 3 8 13 15 21 25
Sample 1 Output
1 2 3 6 8 9 13 13 15 18 18 21 25