HM253 有序归并

来源： 第 253 集 常用排序算法-merge

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

merge 把**两个有序容器**里的元素合并，写入第三个容器，合并后仍然有序。五个参数依次是：第一段的起始与结束迭代器、第二段的起始与结束迭代器、目标容器的起始迭代器。算法在算法头文件中。

注意：

• 两个原容器都必须已经有序，而且**方向一致**（都升序，或都降序）。一个升序、一个降序不能合并出正确结果。
• 目标容器一开始若是空的，不能硬往里塞，程序会崩溃。必须先按两段长度之和 resize，提前分配空间。

先把两段输入各自排成升序（保证方向一致），再按上述规则合并并输出目标容器。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数。当 \(n=0\) 时本行可以是空行。

第三行一个整数 \(m\)。

第四行 \(m\) 个整数。当 \(m=0\) 时本行可以是空行。

输出格式

一行，合并后的升序序列，元素之间单个空格，行末换行。空序列输出空行。

样例

输入 #1

10
0 1 2 3 4 5 6 7 8 9
10
1 2 3 4 5 6 7 8 9 10

输出 #1

0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10

输入 #2

0

3
3 1 2

输出 #2

1 2 3

说明

\(0 \le n,m \le 1000\)，元素绝对值不超过 \(10^9\)。

样例 #1 两段都已升序，目标容量为 \(20\)，合并后仍升序且保留重复值。样例 #2 第一段为空，第二段先排序再合并。