合并过程详解：双指针把两个有序数组合并

给定两个有序子数组，合并用一个结果数组和双指针完成。下面看一个完整可运行实现。

图：merge(L,R) 双指针合并——每次取较小者写入 temp

def merge(left, right):
    out = []; i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

单次合并 O(n)，且“相等取左侧”是稳定性的关键。想验证稳定性，看下一篇。

相关推荐：归并排序为什么稳 · 插入/选择/冒泡排序