1. 合并两个有序序列
每次比较两个序列的头部，取较小者接到输出；一侧耗尽后直接接上另一侧余项。对 p、q 个元素，合并时间 O(p+q)，最多进行 p+q−1 次键比较（两侧都非空）。
2. 稳定合并的 Python 实现
def merge_sorted(left, right, key=lambda x: x):
result, i, j = [], 0, 0
while i < len(left) and j < len(right):
if key(left[i]) <= key(right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
相等时选择左侧 <=，保证来自左半区的旧记录先输出。不要用 Python list.pop(0) 反复删头，移动剩余元素会破坏线性合并成本。
3. 先分割，返回时再合并
归并排序按索引中点拆成两个子序列，对它们递归排序，然后合并。分割不依据键值，故不受“枢轴选得坏”影响。快排的重要工作在递归之前划分，归并的重要工作在递归之后合并。
4. 数组版：共用缓冲区
def merge_sort(a, key=lambda x: x):
result = list(a)
work = [None] * len(result)
def visit(low, high): # 半开区间 [low, high)
if high-low <= 1:
return
mid = (low+high)//2
visit(low, mid)
visit(mid, high)
i, j, k = low, mid, low
while i < mid and j < high:
if key(result[i]) <= key(result[j]):
work[k] = result[i]
i += 1
else:
work[k] = result[j]
j += 1
k += 1
while i < mid:
work[k] = result[i]
i += 1
k += 1
while j < high:
work[k] = result[j]
j += 1
k += 1
for k in range(low, high):
result[k] = work[k]
visit(0, len(result))
return result
使用半开区间 [low, high)。一次创建 n 个位置的 work，所有层共用。函数返回新的有序列表，原输入保持不变；结果副本与缓冲区均为 O(n)。递归栈 O(log n)，总辅助空间仍为 O(n)。
5. 时间复杂度与稳定性
每层合并总长度为 n，共 O(log n) 层，因此最好、平均、最坏时间均为 O(n log n)（本实现不跳过已排序区间）。重复键选左保证稳定。对已有序数据，它不会像优化插入一样自动成为 O(n)。
6. 原书倒序缓冲与哨兵技巧的边界
原书将左半按正序复制、右半按逆序复制，再从缓冲区两端取值，利用最大值作隐式哨兵，减少边界判断。
不能据“相等时选左”就断言这个倒序缓冲变体对记录始终稳定。 左侧耗尽后，若右侧末端有相等记录，左指针可能按倒序访问它们。例如左 [1L]、右 [2A,2B]，缓冲 [1L,2B,2A] 会得到 [1L,2B,2A]。本教材使用显式边界的稳定合并，演示页单独展示该反例，不把技巧当默认实现。
7. 链表版：合并时改链接
class Node:
def __init__(self, value, next_node=None):
self.value, self.next = value, next_node
def merge_links(a, b):
dummy = Node(None)
tail = dummy
while a is not None and b is not None:
if a.value <= b.value:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a if a is not None else b
return dummy.next
def merge_sort_links(head):
if head is None or head.next is None:
return head
slow, fast = head, head.next
while fast is not None and fast.next is not None:
slow, fast = slow.next, fast.next.next
right = slow.next
slow.next = None # 必须断开，否则递归规模不会缩小
return merge_links(merge_sort_links(head), merge_sort_links(right))
快慢指针找中点，然后必须 slow.next = None 断开两半。合并复用原节点，不复制整段记录；dummy 不属于结果。递归版仍有 O(log n) 栈空间，不能说额外空间完全为 0。
8. 外部排序与有序段
内存装不下全部数据时，分块读入、块内排序、写成有序段 run，然后流式合并。二路合并每轮约把段数减半；多路合并用更多缓冲区换更少轮数。重点是顺序读写和块 I/O，不是照搬旧磁带性能数字。
9. Python 内存模拟与真实文件边界
from heapq import merge
def external_merge_demo(data, chunk_size=4):
if chunk_size <= 0:
raise ValueError('chunk_size 必须大于 0')
runs = [sorted(data[i:i+chunk_size]) for i in range(0, len(data), chunk_size)]
return list(merge(*runs)) # 内存模拟；真实外排需把段写文件并流式读取
heapq.merge 可惰性合并有序迭代器。本函数最后转 list、且各段仍在内存，所以只是外排流程模拟，不是处理超大文件的完整外部排序器。真实外排需临时文件、块内存限制、流式解析和资源清理。
10. 示例与常见错误
a = [55,74,3,45,13,87,46,30]
print(merge_sort(a))
print(a) # 原输入未变
print(merge_sorted([30,46,95], [15,26,90]))
print(external_merge_demo(a, chunk_size=3))
忘接剩余项、用 < 破坏相等键稳定性、链表拆分未断链、忽略递归栈、把内存模拟称为真正外排，都是常见错误。