15 归并排序
稳定合并、缓冲、链表与外部有序段
第 01 题 问题 1
归并 [30,46,95] 与 [15,26,90] 的结果？
参考答案
[15,26,30,46,90,95]。
解析
每次比较头部取较小者，一侧耗尽后追加余项。
第 02 题 问题 2
长度 p、q 的两个非空有序序列最多比较多少次？
参考答案
p+q−1 次。
解析
每次比较至少消耗一项；最后一项可直接追加，无需再比较。
第 03 题 问题 3
稳定合并遇到相等键应优先取哪边？
参考答案
左边，使用 <=。
解析
左半原来位于右半前面；优先取左才能保持相等键原顺序。
第 04 题 问题 4
为什么不应反复调用 list.pop(0) 实现线性合并？
参考答案
每次删头会移动剩余引用，可能把整体成本推高到平方级。
解析
使用索引、deque 或链接移动，保持每项只做常数工作。
第 05 题 问题 5
数组归并的拆分是否必须先按键值划分？
参考答案
不需要；按索引中点拆分即可。
解析
重要的有序处理在递归回来后的合并阶段。
第 06 题 问题 6
本教材 merge_sort(a) 会修改原 a 吗？
参考答案
不会，它返回新的结果列表。
解析
result=list(a)，另分配一次 work；与原地简单排序接口不同。
第 07 题 问题 7
数组版归并辅助空间是什么？
参考答案
O(n)。
解析
结果副本、工作数组各 O(n)，递归栈 O(log n)，相加仍是 O(n)。
第 08 题 问题 8
已经升序的数据在本实现中会自动降为 O(n) 时间吗？
参考答案
不会，仍是 O(n log n)。
解析
代码没有跳过已排序区间，每层仍要合并与写回。
第 09 题 问题 9
链表拆分为什么必须 slow.next=None？
参考答案
把原链表真正分成两条独立链，确保递归输入缩小。
解析
如果不切断，左侧仍含全部后半节点，会导致不收敛或结构错误。
第 10 题 问题 10
递归链表归并不使用数组 work，所以额外空间是 O(1) 吗？
参考答案
不是；仍有 O(log n) 递归栈。
解析
合并复用原节点减少 O(n) 缓冲，但不能忽略调用栈。
第 11 题 问题 11
倒序右半缓冲 [1L,2B,2A] 两端取值且相等取左，是否保持右半 2A、2B 的原顺序？
参考答案
不保持；会输出 [1L,2B,2A]。
解析
左半耗尽后，左指针可能沿反向存储的右半输出，相等取左本身不足以保证稳定。
第 12 题 问题 12
external_merge_demo 把有序段全存在内存并 list(merge(...))，算完整外部排序器吗？
参考答案
不算，只是流程模拟。
解析
真实外排需要文件有序段、流式读写、内存与文件句柄管理；多路合并还需按资源选择缓冲与路数。