Merge Sort Algorithm | 合并排序算法

📚 Merge Sort Algorithm | 合并排序算法

Merge sort is one of the most elegant and efficient comparison-based sorting algorithms, widely studied in A-Level computer science courses. It follows the divide-and-conquer paradigm, recursively breaking a problem into smaller sub-problems until they can be solved trivially, then combining the solutions. You can think of it as a systematic way to sort a list by splitting it into individual elements and merging them back in the correct order. This article unpacks every essential aspect of merge sort that an Edexcel A-Level student needs to master, from its algorithmic steps to complexity analysis, implementation considerations, and exam-relevant comparisons.

合并排序是最优雅且高效的基于比较的排序算法之一，在 A-Level 计算机科学课程中广泛学习。它遵循分治范式，递归地将一个问题分解为越来越小的子问题，直到它们可以被简单解决，然后合并这些解。你可以把它想象成一种系统化的列表排序方式：先将列表拆分为单个元素，再以正确的顺序将它们合并回来。本文剖析 Edexcel A-Level 学生需要掌握的合并排序的每一个核心方面，从算法步骤到复杂度分析，从实现注意事项到应试相关的比较。

1. The Divide-and-Conquer Paradigm | 分治范式

At its heart, merge sort relies on the divide-and-conquer strategy. This means a problem is divided into two or more smaller, independent sub-problems of the same type. Each sub-problem is then solved recursively, and their solutions are combined to form a solution to the original problem. In merge sort, the array of n elements is divided into two halves of roughly n/2 elements each. The algorithm keeps dividing until each sub-array contains just one element, which is trivially sorted. Then begins the conquer phase, where merging combines two sorted sub-arrays into one larger sorted array.

合并排序的核心在于分治策略。这意味着一个问题被分割为两个或更多更小的、同类型的独立子问题。然后递归地解决每个子问题，并将它们的解组合起来形成原问题的解。在合并排序中，包含 n 个元素的数组被分成两半，每半大约 n/2 个元素。算法持续分割，直到每个子数组只包含一个元素——这天然就是有序的。随后进入“治”的阶段，通过合并操作将两个已排序的子数组组合成一个更大的有序数组。

2. Algorithm Step-by-Step | 算法分步解析

The classical merge sort algorithm can be described in three high-level steps. Step one: if the array has fewer than two elements, it is already sorted – return it. Step two: otherwise, find the middle index and split the array into left and right halves. Step three: recursively call merge sort on the left half and on the right half. Step four: merge the two sorted halves back into a single sorted array. This process continues until all recursive calls have returned a merged, sorted portion.

经典的合并排序算法可以用三个高层步骤来描述。第一步：如果数组少于两个元素，则它已经有序，直接返回。第二步：否则，找到中间索引，将数组拆分为左半部分和右半部分。第三步：递归地对左半部分和右半部分调用合并排序。第四步：将两个已排序的半部分合并回单个有序数组。这个过程一直持续，直到所有递归调用都返回合并后的有序部分。

The merging procedure uses two pointers, one for each sub-array. The pointer values are compared, and the smaller one is appended to the result. The pointer of the chosen sub-array advances. Once one sub-array is exhausted, the remaining elements of the other are appended. This ensures a stable merge and keeps the time taken proportional to the number of elements being merged.

合并过程使用两个指针，每个子数组一个。比较两个指针指向的值，将较小的值追加到结果中，所选子数组的指针向前移动。当一个子数组的所有元素都被取完，直接将另一个子数组的剩余元素追加。这样保证了稳定的合并，并且合并所需的时间与参与合并的元素数量成比例。

3. Visualising the Recursive Splitting | 递归分割的可视化

Imagine an array [38, 27, 43, 3, 9, 82, 10]. The first split produces left [38, 27, 43, 3] and right [9, 82, 10]. Recursive calls further split until we reach single-element arrays: [38], [27], [43], [3], [9], [82], [10]. The merge stage then builds up sorted arrays: [27, 38] from merging [27] and [38]; [3, 43] from merging [3] and [43]; then merging these to get [3, 27, 38, 43]. The right half yields [9, 10, 82]. Finally, the two sorted halves are merged into the fully sorted array [3, 9, 10, 27, 38, 43, 82]. Drawing this as a tree helps visualise the recursion depth and merge order.

设想一个数组 [38, 27, 43, 3, 9, 82, 10]。第一次分割产生左半 [38, 27, 43, 3] 和右半 [9, 82, 10]。递归调用继续分割，直到得到单元素数组：[38]、[27]、[43]、[3]、[9]、[82]、[10]。然后合并阶段逐步构建有序数组：合并 [27] 和 [38] 得到 [27, 38]；合并 [3] 和 [43] 得到 [3, 43]；接着再合并得到 [3, 27, 38, 43]。右半部分经过合并得到 [9, 10, 82]。最后，两个有序半部分合并为完全有序的数组 [3, 9, 10, 27, 38, 43, 82]。将其画成一棵树有助于可视化递归深度与合并顺序。

4. The Merge Function in Detail | 合并函数的细节

The merge function is the workhorse of merge sort. It assumes it receives two sorted lists, L and R. It creates an empty output list. While both L and R still have elements, it compares the first element of each and removes the smaller one, appending it to the output. After the loop, any leftover elements from L or R are appended, since they are already sorted and larger than all processed elements. This straightforward linear scan makes merging an O(n) operation for two arrays of total length n. Maintaining the relative order of equal elements gives merge sort its stable property.

合并函数是合并排序的主力。它假定接收两个已排序列表 L 和 R。它创建一个空的输出列表。当 L 和 R 都还有元素时，比较它们各自的第一个元素，将较小的元素移出并追加到输出结果。循环结束后，将 L 或 R 中剩余的元素直接追加，因为它们已经是有序的，并且大于所有已处理的元素。这种简单的线性扫描使合并成为总长度为 n 的两个数组上的 O(n) 操作。保持相等元素的相对顺序赋予了合并排序稳定性。

A typical merge function in pseudocode uses while loops and index variables. In an A-Level exam, you might be asked to trace through a merge on given arrays or to write the merge logic in a language like Python. Watch out for off-by-one errors: ensure indices are updated correctly after each removal or copy. Usually, the left and right sub-arrays are created using slicing or copying to avoid in-place complications during merge.

伪代码中的一个典型合并函数使用 while 循环和索引变量。在 A-Level 考试中，你可能需要跟踪给定数组上的合并过程，或者用 Python 等语言编写合并逻辑。小心“差一”错误：确保在每次移除或复制后正确更新索引。通常使用切片或复制来创建左右子数组，以避免在合并过程中产生原地修改的复杂问题。

5. Time Complexity Analysis | 时间复杂度分析

Merge sort exhibits a time complexity of O(n log n) in the best, average, and worst cases. This predictability makes it very attractive. The division creates a recursion tree with a depth of log₂ n because the problem size halves at each level. At each level of recursion, every element is involved in exactly one merge operation. If we sum the work across all levels, we get n elements handled at each of log n levels, giving n log n total comparisons. Thus, even for an array in reverse order, merge sort does not degrade to O(n²) like bubble sort or insertion sort.

合并排序在最好、平均和最坏情况下的时间复杂度均为 O(n log n)。这种可预测性使其非常有吸引力。分割产生一棵深度为 log₂ n 的递归树，因为每层问题的规模减半。在递归的每一层，每个元素恰好参与一次合并操作。将所有层的工作量相加，我们在每一层处理 n 个元素，共有 log n 层，因此总比较次数为 n log n。所以，即使是逆序数组，合并排序也不会像冒泡排序或插入排序那样退化到 O(n²)。

In Edexcel exams, you must be able to justify why merge sort has this complexity. Use the recurrence relation T(n) = 2T(n/2) + O(n) and solve it by the Master Theorem or by drawing the tree of recursive calls. Emphasise that the merge step is linear, and the number of levels is logarithmic. A common mistake is to think merge sort is always faster; the constant factors and memory overhead mean it may be slower for tiny arrays where an O(n²) algorithm with small constant can win.

在 Edexcel 考试中，你必须能够论证为什么合并排序具有这样的复杂度。使用递推关系 T(n) = 2T(n/2) + O(n)，并通过主定理或画出递归调用树来求解。强调合并步骤是线性的，层数是对数级的。一个常见错误是认为合并排序总是更快；常数因子和内存开销意味着对于微小数组，常数较小的 O(n²) 算法可能更胜一筹。

6. Space Complexity and Memory Use | 空间复杂度和内存使用

Merge sort requires additional memory proportional to the size of the input, giving it O(n) auxiliary space complexity. During the merge step, a temporary array is needed to hold the merged result before it is copied back (or a new array is returned). This is a significant drawback when memory is limited or when sorting large data sets in-place is required. Recursive implementations also use O(log n) stack space for the call stack. However, the algorithm is not in-place; the need for extra space is one of the key differences from quicksort, which can be implemented with O(log n) extra space.

合并排序需要与输入大小成比例的额外内存，因此辅助空间复杂度为 O(n)。在合并步骤中，需要一个临时数组来保存合并结果，然后再复制回原数组（或者直接返回新数组）。当内存有限或需要对大数据集进行原地排序时，这是一个显著缺点。递归实现还会为调用栈使用 O(log n) 的栈空间。不过，该算法不是原地排序；对额外空间的需求是它与快速排序的一个关键区别，快速排序可以仅用 O(log n) 额外空间实现。

When tracing merge sort in an exam, be explicit about where the temporary arrays reside. If you are asked to evaluate the suitability of merge sort for embedded systems or huge databases, memory consumption should feature in your answer. You might also discuss in-place merging variants, but the standard merge sort taught at A-Level always uses auxiliary arrays.

在考试中追踪合并排序时，要明确指出临时数组存放在何处。如果被要求评估合并排序在嵌入式系统或超大型数据库中的适用性，内存消耗应当出现在你的答案中。你也可以讨论原地合并的变体，但 A-Level 教学所用的标准合并排序总是使用辅助数组。

7. Stability and Its Importance | 稳定性及其重要性

A sorting algorithm is stable if it preserves the relative order of records with equal keys. Merge sort is stable because during the merge step, when two elements are equal, we take the element from the left sub-array first. Since the left sub-array contains elements that originally appeared earlier, this maintains their original order. Stability matters when sorting data on multiple attributes sequentially. For example, if you sort a list of students by grade and then by name, a stable sort guarantees that the name-order is kept for students with the same grade. Radix sort and bubble sort are also stable; quicksort and heapsort are not naturally stable without modifications.

排序算法如果能够保持相等键值记录的相对顺序，它就是稳定的。合并排序是稳定的，因为在合并步骤中，当两个元素相等时，我们优先取左子数组的元素。由于左子数组包含原先出现更早的元素，这就维持了原来的顺序。当你需要按多个属性顺序对数据排序时，稳定性就很重要。例如，先按年级再按姓名对学生列表排序，稳定的排序保证同年级的学生其姓名顺序得以保留。基数排序和冒泡排序也是稳定的；快速排序和堆排序在没有修改的情况下并不天然稳定。

In Edexcel mark schemes, you may need to state that merge sort is an example of a stable sort. Be ready to explain what stability means and give a scenario where a stable sort is necessary. You can contrast merge sort with quicksort: quicksort may swap elements across partitions and lose stability, whereas merge sort’s controlled merge always preserves original adjacency between equal keys.

在 Edexcel 的评分方案中，你可能需要说明合并排序是一种稳定排序。准备好解释稳定性的含义，并给出一个必须使用稳定排序的场景。可以将合并排序与快速排序进行对比：快速排序可能会跨分区交换元素而丧失稳定性，而合并排序可控的合并过程总是保持相等键值之间原有的前后关系。

8. Recursive Implementation Considerations | 递归实现的考量

A typical recursive merge sort function accepts an array and returns a new sorted array. The base case is an array of length 0 or 1. The recursive case splits the array, calls merge sort on both halves, then merges. In Python, you might write:

一个典型的递归合并排序函数接受一个数组，并返回一个新的有序数组。基准情形是长度为 0 或 1 的数组。递归情形将数组分割，对两半分别调用合并排序，然后合并。在 Python 中，你可能会这样写：

def merge_sort(arr):
if len(arr) <= 1: return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

When tracing on paper, use boxes to show the stack frames and the values being returned. The recursion unwinds in a last-in-first-out manner: the deepest calls (single elements) return first. This is a common topic for trace-table questions. Note that slicing in Python creates new lists, which already account for the O(n) extra space per level. In memory-constrained environments, you might pass indices to avoid copying, but that is beyond the A-Level specification.

在纸上进行跟踪时，用方框表示栈帧和返回的值。递归以后进先出的方式展开：最深的调用（单个元素）最先返回。这是跟踪表类题目的常见考点。注意，Python 中的切片会创建新列表，这已经包含了每层 O(n) 的额外空间开销。在内存受限的环境中，你可以传递索引以避免复制，但这超出了 A-Level 的考纲要求。

9. Comparison with Other Sorting Algorithms | 与其他排序算法的比较

Algorithm	Best	Average	Worst	Space	Stable?
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)	No*
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes

Merge sort’s O(n log n) worst-case performance makes it reliable when the input distribution is unknown or adversarial. Quicksort is often faster in practice due to better cache performance and lower constant factors, but its O(n²) worst case when the pivot is poorly chosen can be a problem. For small n, insertion sort may outperform merge sort because of its simplicity. Merge sort is also the algorithm of choice for external sorting – sorting data stored on disk – because its merge operation naturally handles sequential access patterns.

合并排序 O(n log n) 的最坏情况性能使其在输入分布未知或存在对抗性输入时非常可靠。实践中，快速排序通常更快，因为它具有更好的缓存性能和较低的常数因子，但若枢轴选择不佳，其 O(n²) 最坏情况可能成为问题。对于较小的 n，插入排序可能因其简单性而胜过合并排序。合并排序也是外部排序（对存储在磁盘上的数据进行排序）的首选算法，因为其合并操作能自然处理顺序访问模式。

10. Merge Sort in External Sorting | 合并排序在外部排序中的应用

When data is too large to fit in main memory, external merge sort is used. The algorithm reads chunks that fit in RAM, sorts each chunk (often using an internal sorting algorithm), and writes the sorted chunks (runs) back to disk. Then it merges these runs using a k-way merge, repeatedly reading just the leading blocks of each run into memory and outputting the smallest element. This minimises disk I/O and exploits the fact that merge operations require only sequential access. Standard merge sort’s building blocks map directly to this very practical scenario, which appears in database management systems.

当数据太大无法装进主存时，会使用外部合并排序。算法读取能够放入 RAM 的块，对每个块进行排序（通常使用内部排序算法），并将排序后的块（称为顺串）写回磁盘。然后通过 k 路归并合并这些顺串，反复将每个顺串的前导块读入内存，并输出最小元素。这最大限度地减少了磁盘 I/O，并利用了合并操作仅需顺序访问的特性。标准合并排序的构建模块直接映射到这种非常实用的场景中，数据库管理系统里就会用到。

Understanding this link reinforces why merge sort is fundamental in computer science. In A-Level, you are not required to code an external sort, but you should appreciate that merge sort’s structure makes it ideal when data exceeds available RAM. The concept of runs and multi-way merging can appear in extension questions about the limits of internal sorting algorithms.

理解这一联系可以强化为什么合并排序在计算机科学中如此基础。在 A-Level 中，你不需要编写外部排序的代码，但你应当领会合并排序的结构使其在数据量超出可用 RAM 时成为理想选择。顺串与多路归并的概念可能会出现在关于内部排序算法局限性的拓展问题中。

11. Exam Tips and Common Pitfalls | 应试技巧与常见误区

When answering Edexcel questions, always relate the recursive tree to the complexity. Do not simply state O(n log n); explain that the depth is log n and the work per level is n. Many students confuse merge sort with quick sort, so be precise about the steps: split first, then recursively sort, then merge – whereas quick sort partitions and then recurses. Also, remember to mention that merge sort requires extra memory. A question might ask “explain why merge sort is stable”. Use a concrete example to show that when two elements are equal, the left one is taken first.

在回答 Edexcel 问题时，始终要将递归树与复杂度联系起来。不要仅仅陈述 O(n log n)；要解释深度是 log n，每层的工作量为 n。很多学生把合并排序与快速排序混淆，因此要精确描述步骤：先分割，然后递归排序，最后合并——而快速排序是先分区再递归。此外，记住提到合并排序需要额外内存。题目可能会问“解释为什么合并排序是稳定的”。用一个具体例子来说明当两个元素相等时，左边的元素会先被取出。

In trace tables, always record the values of indices in the merge function, and show the state of the auxiliary array. A typical mistake is forgetting that after one sub-array is exhausted, the remaining elements are simply appended, not compared. Students may also miscount the number of comparisons. The maximum number of comparisons to merge two arrays of total length n is n-1. Practice hand-tracing with arrays of odd length to handle asymmetric splits.

在跟踪表中，始终记录合并函数中各索引的值，并展示辅助数组的状态。一个典型错误是忘记当某个子数组耗尽后，剩余元素是直接追加而无需再比较。学生也可能会数错比较次数。对总长度为 n 的两个数组合并，最多进行 n-1 次比较。练习对奇数长度的数组进行手工跟踪，以处理非对称分割。

12. Key Takeaways and Final Thoughts | 关键要点与最终思考

Merge sort is a classic algorithm that exemplifies divide and conquer. It guarantees O(n log n) time in all scenarios, is stable, and forms the backbone of external sorting. Its main cost is O(n) auxiliary space. As an A-Level candidate, you should be able to explain the algorithm, trace its execution, analyse its complexity, compare it with other sorts, and evaluate its appropriateness for different contexts. Merge sort is not only an exam topic but a timeless design pattern that appears in many areas of computing, from parallel processing to map-reduce frameworks.

合并排序是展示分治策略的经典算法。它在所有情况下都保证 O(n log n) 的时间，具有稳定性，并构成外部排序的基石。其主要代价是 O(n) 的辅助空间。作为 A-Level 考生，你应当能够解释该算法、跟踪其执行过程、分析其复杂度、与其他排序方法进行比较，并评估其在不同场景中的适合程度。合并排序不仅是一个考试主题，也是一种经得起时间考验的设计模式，出现在从并行处理到 Map-Reduce 框架等众多计算领域中。

Published by TutorHao | Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Merge Sort Algorithm | 合并排序算法