hzCPPOJ

【排序】两个升序数组的合并排序

时间限制:  1 s      内存限制:   128 MB
提交:352     正确:224     分值:70

题目描述

现有两个按升序排序的有序数组,需要您定义一个函数能将两个数组合并成一个同样按升序排列的数组。

有同学马上想到了把两个数组合并成一个数组,再进行一次冒泡或者选择排序的方法。虽然能完成任务,但显然辜负了原数列有序的条件。就像我们排队时已经排成了两列有序纵队,现在需要合并成一个纵队。肯定不会把全部同学都散开再一个个排吧?我们会采用什么样的办法,高效的完成任务呢?

请先在纸上画兵布阵,找到合理完整方法,再写代码。


输入

输入分三部分:

第一行是两个用空格隔开的正整数m和n;

第二行是m个元素的升序数组;

第三行是n个无素的升序数组。

**说明:** 数列中不存在两数相同的情况。


输出

输出分两部分:

第一行是合并后的数组长度;

第二行是合并后生成的数组元素,每数字间用空格隔开

样例

样例输入:
4 8 23 56 59 89 2 9 12 18 25 29 55 60
样例输出:
12 2 9 12 18 23 25 29 55 56 59 60 89

提示

## 数据范围

- 1 ≤ m, n ≤ 1000
- 数组元素为整数,且绝对值不超过 10^6
- 保证输入数组严格升序(不存在重复元素)

提交人

AmberXie

来源/分类