排序算法专题（下）|算法篇
# 认识“分治”思想
30 秒速记
- 分治把原问题拆成规模更小、结构相同的子问题，分别求解后再合并结果
- 递归函数必须有可直接求解的基线，并保证每次子问题规模严格缩小
- 切分点和区间开闭要全程统一，合并步骤必须覆盖所有子结果
分治的本质是把一个大问题拆成若干个规模更小、结构相同的子问题，分别求解后再合并成原问题的答案。 使用递归实现时必须设置可直接求解的边界，并保证每次拆分后问题规模都会缩小，否则无法正常结束。落到排序问题里，我一般会重点检查切分区间是否统一，以及合并过程是否完整覆盖每个子问题的结果。
本节我们要学习的两个排序算法都是对“分治”思想的应用。 “分治”，分而治之。其思想就是将一个大问题分解为若干个子问题，针对子问题分别求解后，再将子问题的解整合为大问题的解。
利用分治思想解决问题，我们一般分三步走：
- 分解子问题
- 求解每个子问题
- 合并子问题的解，得出大问题的解
下面我们一起来看看分治思想是如何帮助我们提升排序算法效率的。
面试官追问
追问 1评审一个排序页面时，有人把数组切成两半并分别排好序，却直接拼接左右结果；为什么这还不能算完整的分治？
左右子数组各自有序并不能保证拼接后的整体有序，例如左侧最大值可能大于右侧最小值。分治必须包含分解、求解和整合三个环节，整合规则还要能把子问题的解可靠地转化为原问题的解；缺少合并就只完成了局部求解。
追问 2你要在代码库里实现一种分治排序，递归函数的输入、返回值和终止条件会怎样设计，才能让团队容易验证？
递归函数应接收边界明确的待排序区间或数组，并返回该范围的有序结果；规模缩小到单个元素时直接返回。调用方只依赖“返回结果有序”这一约定，合并逻辑集中处理子结果；若区间开闭混用，可能出现漏项或递归不收敛。
追问 3如果数据规模增大后递归层数成为运行环境的约束，分治思想是否必须放弃？
不必放弃分治，受限的是递归实现形式，而不是分解、求解、合并的结构。可以改成自底向上的迭代流程，从小规模子问题开始逐层合并；代价是控制逻辑更显式，也需要谨慎处理末尾不足一个完整分组的区间。
追问 4线上排序接口偶发返回缺少元素的数组，日志显示每个叶子子问题都正常，你会优先检查分治流程的哪一段？
应优先检查合并阶段，因为叶子结果正确只说明分解和最小子问题求解没有明显异常。核对每个子结果是否都被消费、某一侧耗尽后剩余部分是否保留，并对比分解前后的元素数量；若切分本身存在重叠或空洞，还需回查区间边界。
追问 5同事主张把问题尽可能多切几份，另一位坚持每次只切两份；你会依据什么决定，而不是把“分得更多”当成更高效？
切分数量应服从子问题是否易解以及结果是否易于合并，而不是越多越好。二分通常让边界和合并过程更直观，多分可能减少层数却增加一次整合的参与方；最终还要结合执行环境、数据访问方式和合并成本判断。
# 归并排序
30 秒速记
- 分到单元素，再用双指针合并两个有序段。
- 每层处理
n个元素，共log n层：时间稳定为O(n log n)。 - 数组版本通常需
O(n)辅助空间；相等时先取左段可保持稳定。 - 适合链表、外部排序和需要稳定性的场景。
归并排序会先把数组不断拆到单个元素，再通过双指针把两个有序区间线性合并，真正的排序发生在合并阶段。 每一层都会处理全部 n 个元素，一共有 log n 层，所以时间复杂度稳定为 O(n log n)，数组实现通常还需要 O(n) 辅助空间。合并时若元素相等就先取左侧，可以保持稳定性，因此它适合链表、外部排序或明确要求稳定排序的场景。
回答参考：“归并的核心是两个有序段线性合并。递归只负责划分，真正的排序发生在合并阶段。”
面试官追问
追问 1代码评审中有人说“递归调用完成时数组自然就有序了”，面对页面里的归并排序实现，你会怎样指出概念错误？
递归调用只负责把数组不断划分并取得左右两个有序段，真正建立整体顺序的是合并阶段。若将两个递归结果直接连接，跨边界元素仍可能逆序；因此归并排序的核心约束是每次输入两个有序段，并用线性过程产出一个更大的有序段。
追问 2前端页面需要按时间展示一批记录，你会怎样把“两个有序段线性合并”落实成可检查的代码结构？
为左右有序段各维护一个指针，每轮比较当前元素并把较小者写入结果，随后移动对应指针。任一侧耗尽后追加另一侧剩余元素，代码评审重点检查指针推进和尾部处理；若比较规则不一致，最终顺序或稳定性会偏离预期。
追问 3如果排序对象从普通数组换成通过 next 串联的链表，归并阶段的实现重点会发生什么变化？
链表仍可沿用两个有序段逐项比较的合并逻辑，但结果可通过调整 next 指针连接，不必依赖数组随机访问。寻找切分点和维护链路完整性会成为重点；若断链位置或尾指针处理错误，可能丢失节点或形成环。
追问 4一个超出内存容量的文件需要排序，团队仍想沿用归并思路，你会怎样拆分执行流程？
可以把文件划分为能装入内存的数据块，分别排序并写回，再对这些有序块进行顺序归并。该方案利用归并只需读取各有序段当前元素的特点，但需要管理磁盘读写和多个输入流；块大小及归并路数应受实际资源约束。
追问 5评审会上有人选择归并排序，另一人担心辅助存储；你如何说明这项选型冲突的核心？
归并排序的优势来自稳定地划分，并在线性合并阶段完成排序，时间表现不依赖输入是否已经有序。数组实现通常需要承接合并结果的辅助空间，这是换取清晰线性合并的代价；若内存约束高，应评估数据结构或其他排序方案，而不能忽略空间成本。
# 思路分析
30 秒速记
- 把区间递归二分到单元素，再用双指针线性合并两个已有序子数组
- 合并过程中结果前缀始终有序，且包含两个输入中已经消费的全部最小元素
- 任一侧耗尽后必须追加另一侧剩余元素；切分区间要确保规模严格缩小
归并排序的核心是先把数组递归拆成单元素，再把相邻的有序子数组逐层合并。 单元素天然有序，所以问题会从排序整个数组，转化为反复合并两个有序数组。合并时用双指针取两侧较小的元素，保证结果中已经写入的部分始终有序。切分必须让区间持续缩小，某一侧耗尽后还要把另一侧的剩余元素全部追加进去。
归并排序是对分治思想的典型应用，它按照如下的思路对分治思想“三步走”的框架进行了填充：
- 分解子问题：将需要被排序的数组从中间分割为两半，然后再将分割出来的每个子数组各分割为两半，重复以上操作，直到单个子数组只有一个元素为止。
- 求解每个子问题：从粒度最小的子数组开始，两两合并、确保每次合并出来的数组都是有序的。（这里的“子问题”指的就是对每个子数组进行排序）。 合并子问题的解，得出大问题的解：当数组被合并至原有的规模时，就得到了一个完全排序的数组
面试官追问
追问 1页面把数组递归切到单元素；如果有人改成切到空数组才停止，代码会出现什么现象，为什么不符合这里的分治框架？
若非空数组的切分不能保证两侧都严格缩小，递归可能反复处理同一范围，最终导致调用栈耗尽。单元素本身已经有序，是可直接求解的子问题；终止条件还应覆盖空数组，避免边界输入进入没有意义的继续切分。
追问 2实现归并排序时，左右递归结果已经各自有序，你会怎样写合并循环并证明它没有遗漏元素？
合并时为左右数组分别维护指针，每轮取两个当前元素中较小者加入结果，并只推进被取值的一侧。循环结束说明至少一侧已耗尽，此时必须把另一侧尚未消费的后缀完整追加；同时核对输出长度等于两侧长度之和，才能及时发现漏项。
追问 3如果需求要求排序结果保留相等记录的原始先后顺序，合并阶段的比较条件应该怎样处理？
相等时应优先选择左侧有序段中的元素，因为左侧元素在原数组中整体更靠前，这样才能保持相对顺序。若代码使用严格小于并在相等时取右侧，排序值仍正确，但稳定性会被破坏；前提是此前各层合并也遵守同一规则。
追问 4线上出现“数组长度正常但局部逆序”，单元素和双元素用例都通过，你会怎样定位是切分还是合并的问题？
记录每层左右输入及合并输出，先确认两个输入段是否各自有序，再检查输出中跨段边界的元素顺序。若输入无序，故障来自更深层递归；若输入有序而输出逆序，则重点核对比较方向、指针推进以及剩余后缀的追加逻辑。
追问 5同事提出省掉合并步骤，先递归排好左右两半，再交换两半的位置；在什么条件下这个方案才可能正确？
只有能够证明一侧所有元素都不大于另一侧所有元素时，直接拼接或整体交换才可能得到有序结果。一般输入并不存在这样的跨段关系，因此仍需逐项合并；额外扫描边界只能识别少数可直接连接的情况，不能替代通用合并。
# 真实排序过程演示
30 秒速记
- 把区间递归二分到单元素，再用双指针线性合并两个已有序子数组
- 合并过程中结果前缀始终有序，且包含两个输入中已经消费的全部最小元素
- 任一侧耗尽后必须追加另一侧剩余元素；切分区间要确保规模严格缩小
这个数组会先从规模 8 逐层拆到规模 1，再按 1→2→4→8 的顺序合并成有序数组。 例如 [8,7] 合并为 [7,8]，相邻结果继续合并，最终得到 [1,2,3,4,5,6,7,8]。代码里的递归负责完成有去有回的分割过程，双指针负责合并两个已有序数组。合并时若一侧已经遍历完，另一侧剩余部分本身有序，可以直接拼到结果末尾。
