简化题意

给出两个长度分别为$n, m$的序列（每一个序列都有序），请将它们合并之后排序。

分析

此题是归并排序的前奏，强烈建议搭配课程使用。

我们已经知道，快速排序的复杂度为$O(n\log n)$，但此题数据很强，数据范围为$n < 10^7$，用$O(n\log n)$的复杂度在200万到500万的数据时就会爆炸。

而为了降低时间复杂度，这一题我们可以用这个方法：

举个例子：序列1：1 2 5 序列2：1 3 4

第一次比较：a[0] = 1 b[0] = 1，1=1，将a[0]放入结果序列中

第二次比较：a[1] = 2 b[0] = 1，2>1，将b[0]放入结果序列中

第三次比较：a[1] = 2 b[1] = 3，2<3，将a[1]放入结果序列中

第四次比较：a[2] = 5，b[1] = 3，5>3，将b[1]放入结果序列中

第五次比较：a[2] = 5，b[2] = 4，将b[2]放入结果序列中。

这里友情给出合并序列的一部分代码：

int ind1 = 0, ind2 = 0, ind3 = 0; // ind1 是 a 数组的比较下标，ind2 是 b 数组的比较下标，ind3 是 c 数组的存储下标。
while(ind1 < n && ind2 < m){ // 当两个数组均未被比较完填入时
	if(a[ind1] <= b[ind2]){ // a 数组对应项小于或等于 b 数组对应项，取等号是为保证稳定性
		c[ind3++] = a[ind1++]; // 记录
	}
	else{
		c[ind3++] = b[ind2++]; // 记录
	}
}

知识彩蛋1号：各种时间复杂度的超时输入规模（以1亿为界限，相当于时限1s；按复杂度从小到大排序）

如果你用到了数据范围超过你所计算的复杂度超时输入规模的方法，请想另一种方法或尝试优化；不建议使用$O(n^3)$及以上的复杂度，建议最多只使用双重循环。