⚠️ 换一个输入，它就露馅了
同一个 msort_bad，换成 [0, 1, 2, 4, 3]： def msort(a): if len(a) <= 1: return list(a) m = len(a) // 2 L
自己写：把合并的最后一步补上
补全归并的收尾——循环出来时，两边一定有一边还剩着。
🔴 120 种输入里，错的那版有几种照样对
把五个元素的全部 120 种排列都喂给 msort_bad，数一数有多少种它照样给出了正确结果。
交付：基线 / 归纳步 / 不丢元素
把归纳证明的三件事各写成一次检查。归纳步拿 [1,4,6] 和 [2,3,5] 两个已经排好的半边去合并；"不丢元素"拿 [0,1,2,4,3] 验。
「下界」说的是什么
说比较排序有一个下界，意思是【0】。
⚠️ 决策树的叶子对应什么
把一个比较排序画成决策树，每个叶子对应【0】。
这个下界管的是哪一种情况
比较排序的这个下界，说的是【0】。
五个元素的下界是多少
五个元素一共有多少种排列？装下这么多叶子的二叉树至少多高？ import math from itertools import permutations def merge_cmp(a): """归并
两种排序的最坏比较次数
把五个元素的全部 120 种排列都跑一遍，插入排序和归并排序各自最坏比了多少次： import math from itertools import permutations def merge_cmp(a): "&qu
🔴 有输入低于下界，这矛盾吗
下界算出来是 7。数一数 120 种输入里，归并排序用了不到 7 次就排完的有几种，再报出最坏的那一档。