合并有序数组。

核心回答

利用两个数组已经有序的条件，用双指针逐个确定下一项，时间为 O(m+n)。 允许返回新数组时，从两边开头比较，把较小者追加到结果；一边用完，再接上另一边剩余部分。

如果要求写回第一个数组，且其尾部已预留足够空间，就从后往前比较有效区间的末尾，把较大者写到结果末尾。这样不会覆盖尚未读取的输入，额外空间可以降到 O(1)。

返回新数组：通用的双指针合并

设输入按非递减顺序排列，保留重复元素，不修改输入。下面用 Python 实现：

def merge_sorted(a: list[int], b: list[int]) -> list[int]:
    i = j = 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1

    while i < len(a):
        result.append(a[i])
        i += 1
    while j < len(b):
        result.append(b[j])
        j += 1
    return result

例如 [1,3,5] 和 [2,3,6] 合并为 [1,2,3,3,5,6]，两个 3 都保留。相等时先取 a，还能保持相等元素在各输入内的次序，以及 a 中相等项先于 b 中相等项。

每轮开始时，结果包含全部已处理元素且保持有序。剩余元素的最小值一定在两个未处理部分的开头，因此选其中较小者，就得到全体剩余元素的最小值。一边耗尽后，另一边本来有序，可以直接接上。

两个指针各自只走一遍，总时间 O(m+n)；结果占 O(m+n) 空间，除输出外只用常数个变量。空数组、负数和重复值都适用。

尾部预留空间：倒序原地合并

常见的另一种约定是：nums1 长度为 m+n，前 m 项有效；nums2 长度为 n，全部有效；结果写回 nums1。

有效长度由 m 决定，不能靠是否为零识别。 零也可以是真实数据，尾部占位值不参与比较。

def merge_inplace(
    nums1: list[int], m: int, nums2: list[int], n: int
) -> None:
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

以 nums1=[1,3,5,0,0,0]、m=3、nums2=[2,3,6] 为例，先把 6 放在末尾，再比较 5 和 3。每次确定的是剩余元素中的最大值，已写好的后缀就是最终结果的后缀。

只要 nums2 还没用完，就有 write=i+j+1>i，写入位置在 nums1 未处理前缀右侧，所以不会踩掉待比较的数据。nums1 先耗尽时继续复制 nums2；nums2 先耗尽时，nums1 剩余前缀已经正确，可以结束。

该版本时间 O(m+n)、额外空间 O(1)，依赖尾部预留空间，不能直接套到两个均无空位且要求写入其中一个定长数组的情况。

为什么不逐项插入或重新排序

逐个插入并反复定位、搬移后缀，可能造成二次量级的工作；具体成本取决于实现和数据分布。合并后调用排序也能得到正确结果，自适应排序可能利用已有的有序段，因此不能一概断言这里一定付出 O((m+n)log(m+n)) 时间。手写题可以直接说明双指针如何利用有序条件保证线性合并，无需依赖某个排序实现。

如果是多个有序数据流，可维护各流当前候选，用最小堆做多路归并。Python 的 heapq.merge() 返回惰性迭代器，要求输入流本来就有序。两个数组的手写题，用双指针更直接。

现成接口也有存储约定。例如 C++ 的 std::merge 要求输出不与输入重叠，不能把“库函数能合并”理解为支持上述尾部原地写回。

参考资料