1. 核心物理动作合并Merge归并排序只在做一件事而且只做这一件事把两个已经在内存里连续有序的块合并成一个更大的连续有序块。输入物理条件数组a中区间[lo, mid]已经按升序排列。区间[mid1, hi]已经按升序排列。这两个区间在物理内存上是相邻的中间没有空隙但它们的值域可能有重叠。合并动作的物理步骤把[lo, hi]这一段全部复制到辅助数组aux的对应位置。这是一个连续内存拷贝。设置两个指针i指向aux中左半部分的起始loj指向aux中右半部分的起始mid1。设置指针k指向原数组a的起始位置lo。循环比较aux[i]和aux[j]。如果aux[i] aux[j]把aux[i]写回a[k]i。否则把aux[j]写回a[k]j。k。当i超过mid左半耗尽把右半剩余的全部连续拷贝到a[k..hi]。当j超过hi右半耗尽把左半剩余的全部连续拷贝到a[k..hi]。关键物理事实合并过程中i、j、k都是单向递增的不存在回退。对a的写操作是顺序的对aux的读操作也是顺序的分别在两个连续段内顺序前进。这种访问模式在现代 CPU 上的缓存命中率很高。必须使用aux的原因如果直接在a内部覆盖会丢失尚未读取的数据。aux充当临时工作区。2. 分治结构递归负责组织合并顺序归并排序的递归函数sort(a, lo, hi)本身不做任何比较和移动它只做三件事如果hi lo区间长度 ≤ 1直接返回。计算mid递归调用sort(a, lo, mid)保证左半有序。递归调用sort(a, mid1, hi)保证右半有序。调用merge(a, lo, mid, hi)合并两个有序块。物理执行轨迹这个递归过程生成的是一棵二叉树。叶子节点是长度为 1 的区间天然有序。从叶子向上每两个相邻的已排序块被合并成更大的块直到根节点合并整个数组。一个递归调用的方法比较的部分在merge函数里。具体使用时的表现是例如有16则分0~7→0~3→0~1→0~1排序好2~3→0~1、2~3排序好0~3→4~7→0~7接着8~15也是按照这个顺序最后再把0~7和8~15合并3. 复杂度来源为什么是N log N层数每次把区间切成两半直到长度为 1。切分次数为log₂N向上取整。递归树的高度是log₂N。每层的总工作量在每一层即每个递归深度所有被合并的区间加起来正好覆盖整个数组一次。每个元素在每层恰好参与一次合并作为左半或右半的一部分。单次合并中每个元素被比较一次可能被移动一次因此每层的工作量与N成正比。总比较次数每层N次比较共log₂N层结果是N log₂N。总数组访问次数每次合并需要复制到aux读a、写aux和归并回a读aux、写a。每个元素在每层被访问约 6 次具体实现略有浮动所以总访问次数为6N log₂N。ppt上写为nlgn但lg是log2的简写而不是log10的。D是成本函数式子右侧N的意义是合并两个被等分的数组需要的比较成本。D是归并排序成本函数Cost Function的符号。在这个递推式里D(N)表示对规模为N的数组进行排序所需要的总操作次数这里的“操作”在 PPT 这个具体推导语境里指比较次数。2D(N/2)表示两个规模为N/2的子排序成本归并排序分治后要分别解决左右两半。N表示合并这两个已经排好序的子数组时进行比较的成本。在归并操作中每次合并最多需要N次比较最坏情况。D(1) 0表示数组大小为 1 时已经有序不需要比较。整个递归式解出来就是D(N) N log₂ N。PPT 用D而不是C大概只是因为字母C已经用在其他地方比如C(N)表示常数这里就用D来代表“复杂度Complexity”或通用的“成本函数Cost”。你只需要知道这个符号指的就是“归并排序完成这一层任务要执行多少次内循环逻辑”。不需要把它看成一个特殊的概念它就是你想的那个“算时间的变量”。4. 自底向上的迭代版本MergeBU下节内容自顶向下版本用递归来决定合并顺序。自底向上版本直接用循环模拟这个过程设置子数组大小sz 1。当sz N时遍历数组步长为2 * sz对每对相邻的、大小为sz的块调用merge。sz sz * 2。物理区别自顶向下和自底向上产生的合并顺序不同但比较次数和访问次数完全相同。自底向上不需要递归调用栈但它需要额外计算边界Math.min(lo sz sz - 1, N - 1)来处理数组末尾剩余的不完整块。PPT 指出自底向上在典型系统上比自顶向下慢约 10%原因是递归版本在缓存利用和分支预测上略有优势具体与编译器和 JVM 实现有关。5. 比较器Comparator和稳定性比较器排序算法本身不定义“什么是小于”。它依赖Comparable接口自然顺序或Comparator对象外部顺序。当使用Comparator时less函数变为c.compare(v, w) 0其中c是传入的比较器对象。这种方式使得“比较逻辑”与“排序算法”完全解耦允许同一组数据按不同字段排序如按姓名或按学号。稳定性归并排序是稳定排序。稳定性的物理含义是如果两个元素的主键相等它们在排序后的相对顺序与排序前相同。归并操作保证稳定性的方式是在比较aux[i]和aux[j]时如果两者相等优先取左半部分的元素aux[i]。因为左半部分的元素在原始数组中位于右半部分元素之前优先取左半就保留了原始相对顺序。这是归并排序与快速排序的一个重要区别快速排序的原地分区操作会破坏稳定性。6. 空间使用归并排序不是原地排序。它需要额外N个引用大小的空间来存放aux数组在 Java 中aux是一个与a同类型的引用数组占8N字节不复制对象本身。这个空间在sort开始时一次性分配在整个排序过程中复用不会被多次分配和释放。归并排序的物理本质已经完整了。如果你需要对merge代码中的边界条件i mid、j hi做逐行拆解或者对递归树的高度推导有疑问直接指出即可。一、归并排序针对小数组情况的优化Q这个是什么意思A这一页的意思是归并排序在处理“小数组”时是低效的所以我们要在递归到底之前“中途跳车”改用插入排序来处理这些小段。核心逻辑就是代码里那个if判断平时递归排序会一直切分到数组长度变成 1hi lo才停止。但是这里加了一个截止阈值Cutoff如果当前要排序的子数组长度小于等于7就不继续递归切分了而是直接调用Insertion.sort来处理这一段。你可以直接把它理解为一种“止损策略”1. 为什么归并排序在小数组上“亏本”物理开销归并排序要执行merge操作而merge必须把数据复制到aux辅助数组再复制回来。这涉及两次内存读写。递归栈开销为了排 8 个元素递归要分裂 3 层产生多次函数调用。对比插入排序虽然算法复杂度高O(N²)但当N非常小比如 7时它的常数因子极小——它不需要辅助数组没有递归调用就是几行简单的循环和赋值。在 CPU 看来那点平方开销远小于归并排序的“搬运 函数调用”开销。2. 怎么确定是 7这来自于经验调优实验数据。Sedgewick 在写这本书的时候做过大量测试发现在大多数现代系统上当子数组大小在 7 到 15 之间时切换到插入排序总运行时间能缩短10%~15%。这 7 只是个示例数字实际代码里一般设成 10 到 15。3. 这在代码里的物理执行路径当递归切分到lo和hi的差值小于 7 时它不会再去计算mid切半分。它直接交出控制权给插入排序插入排序在这一小段连续内存上跑完排序。然后递归回溯上层的大块合并依然正常进行。你可以这样理解归并排序负责把大象切分成小块最后那一丁点肉屑懒得用大刀切了直接用小刀插入排序处理。这是一个被证明有效的算法性能优化手段也是最常见的递归分治算法优化技巧之一。注意这个函数是被递归调用的大数组会被切分成小数组小数组再次调用此函数。所以if对一开始较大数组不起作用对内里的小数组生效对局部小数组使用插值排序二、归并排序在时间上优化Q你看看这个很有趣的代码它在sort函数里面是在对aux数组进行拆分但是由于每个sort它都会正确的计算lowmid还有high这三个指针所以同时也对a数组进行了拆分。不如说在这个意义上由于aux数组和a数组大小等同所以它们在拆分计算的时候是等同的。而之所以在merge函数里面要进行调转回到正常的aaux顺序是因为这里要进行内容的搬运。那么我认为这里有被优化到的点就是我们不再需要把a数组复制进aux数组再把数据从aux里面搬回a数组而是直接把装有内容的aux数组返回作为结果是这样吗A是理解完全正确。这恰好是这个优化的核心物理目的——消除显式的复制循环。你看到的那段代码是在玩一个把戏递归的每一层a和aux的角色谁是源谁是目标都是互换的。我来把这句话拆开让你彻底看清它怎么运作的1. 传统归并排序的“复制”成本在哪以前的代码是先aux[k] a[k]复制到辅助数组。合并时再从aux读写回a。每层每个元素要被搬运2 次复制进aux一次归并回a一次。2. 这段代码怎么“省掉复制”仔细观察merge函数的参数merge(a, aux, lo, mid, hi)。注意在这个实现里合并的结果是写到第二个参数aux里去的而不是写回第一个参数a。也就是说它把两个有序的源数组块来自a合并到目标数组aux中。现在看sort函数递归时怎么做的sort(aux, a, lo, mid);—— 它对aux的左半边进行排序用a作为辅助。merge(a, aux, lo, mid, hi);—— 它把a的两个有序半段合并到aux里。物理执行过程追踪一个 4 元素数组顶层调用sort(a, aux, 0, 3)。它切分左右递归调用sort(aux, a, 0, 1)和sort(aux, a, 2, 3)这回轮到aux被排序了。底层递归把aux里的小段排好序把结果写回a中。回到顶层现在a的左右两半是有序的。顶层的merge(a, aux, 0, 1, 3)执行把a的两个有序半段合并写进aux里。最终状态排序好的完整数据就待在aux数组里而不是a数组里。3. 回答你的结论“直接把装有内容的 aux 数组返回作为结果”物理上完全成立但具体实现要看调用方怎么收场因为一开始aux就已经被初始化并且复制了a的初始内容或者大小相同经过这样“角色互换”的递归合并后最终结果确实落在aux中。调用者main函数直接使用aux作为排序后的结果就可以了或者System.arraycopy(aux, 0, a, 0, N)拷回去但后者又加了一次拷贝成本。所以工业实现通常直接让调用方持有aux作为最终有序数组或者设计 API 时让sort函数返回aux的引用。代价它没省空间依然需要N大小的辅助数组它省的是 “每层多搬运一次数组元素” 的时间——这在数据量大时相当可观。你看到的这个代码其实是归并排序在“空间换时间”策略下对“时间”的进一步压榨。你感觉到的“返回aux”正好说中这个优化的精髓。