介绍
归并也称为 合并，归并排序是一种基于 分治法（Divide and Conquer） 的排序算法，思想是：
分（Divide）：把待排序的数组 不断拆分成两个子数组，直到每个子数组 只有 1 个元素（单个元素天然有序）。
治（Conquer）：把拆分后的 子数组两两合并，合并时按照从小到大（或从大到小）的顺序排列，最终得到一个有序数组。
例子
假设我们有一个初始数列为
{8, 4, 5, 7, 1, 3, 6, 2}
整个归并排序的过程如下图所示
每次合并时，比较大小，比如：将小的放在前面
可以看到这种结构很像一棵 完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。
分阶段可以理解为就是递归拆分子序列的过程，递归深度为 O(nlog₂n)
参考：
https://blog.csdn.net/justidle/article/details/104203958
上图最后一步：合并两个有序数组流程
如上图中的最后一次合并，要将 [4,5,7,8] 和 [1,2,3,6] 两个已经有序的子序列，合并为最终序列 [1,2,3,4,5,6,7,8]，步骤如下：
比较次数
比较 n/2 次，n 是总元素的个数
参考：
https://blog.csdn.net/justidle/article/details/104203958
时间复杂度
O(nlog₂n)
执行 log₂n 趟，每趟比较 n 次（不到 n 次）
时间复杂度-最好
O(nlog₂n)
时间复杂度-最坏
O(nlog₂n)
空间复杂度
O(n)
有上图可知，需要额外的数组存储合并结果
是否稳定
稳定
合并时遇到 两个元素相等， 会优先取左数组的元素
题
两个递增序列 A 和 B 的长度分别为 m 和 n（m<n 且m与n接近），将二者归并为一个长度为 m+n 的递增序列。当关系为（）时，归并过程中元素的比较次数最少。
分析
选项A
- a1 与 b1比较，a1 小，temp=[a1]
- a2 与 b1比较，a2 小，temp=[a1,a2]
- a3 与 b1比较，a3 小，temp=[a1,a2,a3]
- …..
- am 与 b1比较，am 小，temp=[a1,a2,a3,…am]
比较 m 次，此时 b1 比 A 所有元素大，就不需要比较了，将 B 序列中元素复制到 temp 中，即：temp=[a1,a2,a3,…am,b1,b2,…bn]
选项B
- b1 与 a1比较，b1 小，temp=[b1]
- b2 与 a1比较，b2 小，temp=[b1,b2]
- b3 与 a1比较，b3 小，temp=[b1,b2,b3]
- …..
- bn 与 a1比较，bm 小，temp=[b1,b2,b3,…bn]
比较 n 次，此时 a1 比 B 所有元素大，就不需要比较了，将 A 序列中元素复制到 temp 中，即：temp=[b1,b2,…bn,a1,a2,a3,…am]
题干给出 m<n，所以错
选项C
当 bm 比 am大时，就不需要比较了，前面有 m 个 a，m-1 个 b，即：比较 m + m - 1 = 2m - 1 次
选项D
当 bm+1 比 am大时，就不需要比较了，前面有 m 个 b，和 m 个 a ，即：比较 2m 次
答案
题中给出 m<n，所以选择 A
参考：
https://blog.csdn.net/justidle/article/details/104203958