15 归并排序
稳定合并、缓冲、链表与外部有序段
本节 12 题。先独立给出结论和理由，再对照解析；新增题与此前题目统一编号。涉及标签时，标签只表示记录身份。
第 01 题
问题 1
归并 [30,46,95] 与 [15,26,90] 的结果？
第 02 题
问题 2
长度 p、q 的两个非空有序序列最多比较多少次？
第 03 题
问题 3
稳定合并遇到相等键应优先取哪边？
第 04 题
问题 4
为什么不应反复调用 list.pop(0) 实现线性合并？
第 05 题
问题 5
数组归并的拆分是否必须先按键值划分？
第 06 题
问题 6
本教材 merge_sort(a) 会修改原 a 吗？
第 07 题
问题 7
数组版归并辅助空间是什么？
第 08 题
问题 8
已经升序的数据在本实现中会自动降为 O(n) 时间吗？
第 09 题
问题 9
链表拆分为什么必须 slow.next=None？
第 10 题
问题 10
递归链表归并不使用数组 work，所以额外空间是 O(1) 吗？
第 11 题
问题 11
倒序右半缓冲 [1L,2B,2A] 两端取值且相等取左，是否保持右半 2A、2B 的原顺序？
第 12 题
问题 12
external_merge_demo 把有序段全存在内存并 list(merge(...))，算完整外部排序器吗？