归并排序（Merge Sort）是建立在归并操作之上的一种稳定排序算法，其核心思想是分治法（Divide and Conquer）。在软考大纲中，归并排序属于中级软件设计师《数据结构与算法》章节的必考内容，同时在系统分析师、系统架构设计师的综合知识题中也会以比较排序算法的方式反复出现。教材对归并排序的正式定义可以概括为：将待排序序列递归地划分为长度大致相等的两个子序列，分别对这两个子序列进行排序，然后将两个已经有序的子序列合并为一个完整的有序序列。
理解这一定义的关键，在于把握"归并"（Merge）这个动作本身。归并指的是把两个或两个以上已经有序的序列，合成一个仍然有序的新序列的过程。归并排序之所以能够成立，是因为它假设了这样一个前提：如果两个子序列本身已经各自有序，那么通过一次线性的扫描比较，就能够在 O(n) 的时间代价内把它们合并成一个完整有序的序列。这一前提是整个归并排序算法能够把复杂度稳定地控制在 O(nlogn) 级别的根本原因。
在软考教材的术语体系中，归并排序涉及几个必须准确掌握的概念。第一个是"有序段"（run），指的是序列中已经排好序的连续片段；初始状态下，每个单独的记录都可以视为一个长度为 1 的有序段。第二个是"归并趟数"，指的是从初始的有序段出发，经过多少次两两归并才能最终得到一个完整的有序序列。第三个是"二路归并"，即每次只把两个有序段合并为一个有序段，这是软考命题中最常见、也是考试计算题默认采用的归并方式。
与二路归并相对的还有多路归并。二路归并每次处理两个输入序列，多路归并则同时处理三个或更多个输入序列。软考中级通常只考二路归并，多路归并主要出现在系统分析师和数据库系统工程师的"外部排序"相关知识里，作为提高磁盘归并效率的手段出现。考生务必先把二路归并的每一个细节吃透，再去理解多路归并的推广形式，否则容易在概念层面对应不上。
归并排序有两个必须死记硬背、且经常被命题人拿来和其他排序算法对比的结论。第一个结论是：归并排序是稳定排序。所谓稳定，指的是当待排序序列中存在两个关键字值相等的记录时，排序完成后这两个记录的相对先后次序保持不变。这一性质来源于归并操作本身的实现细节——在合并两个有序段时，当左段当前元素与右段当前元素的关键字相等，归并算法总是优先输出左段的元素，从而保证了稳定性。第二个结论是：归并排序的时间复杂度在最坏、最好、平均三种情况下都是 O(nlogn)。这一"三态一致"的特性是归并排序区别于快速排序的重要标志——快速排序虽然平均是 O(nlogn)，但在最坏情况下会退化到 O(n²)。
与稳定性和时间复杂度相伴的，是归并排序的空间复杂度结论：归并排序需要额外的 O(n) 辅助存储空间，因此它是一种非原地排序（out-of-place sorting）。这一点在软考命题中极为关键，因为它直接决定了归并排序与堆排序、快速排序在使用场景上的分界——堆排序是原地排序且不需要额外空间，归并排序则必须付出 O(n) 的空间代价来换取稳定性。考生如果把"稳定"和"原地"这两个属性记混，就会在做比较类选择题时失分。
从算法地位上看，归并排序是所有基于比较的排序算法中第一个在理论上被证明能够达到 O(nlogn) 下界的算法。信息论意义上，任何基于元素比较的排序算法，其决策树高度至少为 log₂(n!)，而 log₂(n!) 与 nlogn 同阶，这便构成了基于比较排序的时间复杂度下界 O(nlogn)。归并排序和堆排序恰好都触及了这一下界，因而被称为渐进最优的比较排序算法；而基数排序、计数排序等非比较排序之所以能突破 O(nlogn)，正是因为它们放弃了"只能通过比较来确定次序"这一前提，转而利用关键字的取值范围信息。理解这一理论背景，有助于考生从更高的视角把握归并排序在整个排序算法家族中的坐标位置。
要真正理解归并排序，就不能停留在"先拆再合"这种表面描述上，而必须深入到分治法的执行框架、归并操作的逐元素比较过程，以及递归树如何推导出 O(nlogn) 这三个层面。
分治法的本质，是把一个规模较大的原问题，分解成若干个规模较小的、结构相同的子问题，递归地求解这些子问题，再把子问题的解合并成原问题的解。归并排序是分治法最标准的教科书范例，它把这一框架落到了三个明确的阶段。分解阶段：把长度为 n 的待排序序列一分为二，得到两个长度大致相等的子序列，若 n 为奇数，则左段多一个元素。求解阶段：对这两个子序列分别递归地执行归并排序，直到子序列的长度为 1 时，递归自然终止——因为长度为 1 的序列天然有序。合并阶段：将两个已经有序的子序列，通过二路归并操作合并成一个有序序列，这一过程自底向上逐层回溯。
这里有一个容易让考生困惑的点：归并排序的"分解"其实是逻辑上的划分，而不是物理上的数据搬移。在经典的递归实现中，分解阶段并不真正把数据拷贝成两份，而只是通过下标范围（low、mid、high）来划定两个子区间，真正的数据移动只发生在合并阶段。理解这一点，有助于解释为什么归并排序的空间开销主要来自合并阶段需要的临时数组，而不是分解阶段。
二路归并的合并过程是整篇文章的技术核心，也是软考命题人最爱挖坑的地方。假设有两个已经有序的序列 A 和 B，长度分别为 m 和 n，现在要把它们合并成一个长度为 m+n 的有序序列。合并算法维护三个游标：游标 i 指向序列 A 的当前元素，游标 j 指向序列 B 的当前元素，游标 k 指向输出临时数组的当前位置。每一轮比较，算法比较 A[i] 与 B[j] 的大小，把较小的那个元素写入临时数组的第 k 个位置，并让对应的游标 i 或 j 后移一位，同时 k 也后移一位。当 A 或 B 中任意一个序列的所有元素都被取尽时，把另一个序列剩余的元素整体复制到临时数组的末尾。
这一过程中的关键细节在于"稳定性的来源"。当 A[i] 与 B[j] 的值相等时，归并算法必须选择优先输出 A[i]，也就是优先输出左侧序列的元素。正是这一条"等于时取左"的规则，保证了归并排序是稳定的。如果实现时误写成"等于时取右"，归并排序就会变成不稳定排序。软考的排序稳定性判断题，很多时候就是围绕这一类实现细节设问，考生不仅要记住"归并排序稳定"的结论，还要知道它为什么稳定。
用一个具体例子可以把合并过程看得更清楚。设左段为 [2, 4, 6]，右段为 [1, 3, 5]，三个游标从各自头部起步：先比较 2 与 1，1 较小，写入临时数组，右游标后移；再比较 2 与 3，2 较小，写入，左游标后移；接着比较 4 与 3，3 较小，写入，右游标后移；随后比较 4 与 5，4 较小，写入，左游标后移；再比较 6 与 5，5 较小，写入，右游标后移；此时右段已空，把左段剩余的 6 直接复制到末尾，得到 [1, 2, 3, 4, 5, 6]。整个合并过程共进行了五轮比较，恰好等于两段元素总数减一，这也印证了合并操作 O(m+n) 的线性代价。若左右两段出现相等元素，例如左段含 3、右段也含 3，则按"等于时取左"规则先输出左段的 3，从而维持了相对次序。
归并排序的时间复杂度为什么是 O(nlogn)，可以通过递归树来严格推导。把递归过程看作一棵二叉树：树的根节点代表对长度为 n 的序列的排序，它分裂出两个子节点，分别代表对长度为 n/2 的两个子序列的排序，如此逐层向下，直到叶子节点代表长度为 1 的序列。整棵树的高度是 log₂n，因为每一层都把序列长度减半。在每一层上，所有节点所覆盖的元素总数加起来恰好是 n，而合并操作对每一层的总工作量是 O(n)——因为每一层都要把所有 n 个元素完整地扫描并写入一次。于是总时间 = 层数 × 每层工作量 = log₂n × O(n) = O(nlogn)。
这一推导的妙处在于，它揭示了一个重要事实：无论输入序列的初始顺序如何，归并排序的分解和合并步骤都是机械固定的，不受数据分布影响。分解总是对半切，合并总是逐元素比较并线性扫描，没有任何一步会因为数据已经有序而跳过。正因如此，归并排序才具有"最坏、最好、平均三态都是 O(nlogn)"的特性，这与快速排序形成了鲜明对比——快排的性能高度依赖划分点的选择，最坏情况下递归树会退化成一条链。
归并排序不是只有一种写法，它在实现方式、归并路数和应用场景上都有丰富的变体，这些变体同样是软考命题的素材来源。
按照归并的驱动方式，归并排序可以分为自顶向下和自底向上两种实现。自顶向下实现就是前文所述的标准递归写法：先递归地分割，再在回溯时合并，代码结构清晰，与分治思想一一对应。自底向上实现则完全摆脱递归，改用迭代：第一趟把相邻的长度为 1 的元素两两归并成长度为 2 的有序段，第二趟把相邻的长度为 2 的有序段两两归并成长度为 4 的有序段，
本篇完！