Mergesort

定义 Definition

归并排序：一种基于“分治法”的稳定排序算法。它将序列不断拆分成更小的子序列，分别排序后再按顺序“归并”成一个有序序列。典型时间复杂度为 **O(n log n)**，通常需要额外的线性辅助空间（数组实现时常见）。

发音 Pronunciation (IPA)

/ˈmɝːdʒ sɔːrt/

例句 Examples

Mergesort is stable and runs in O(n log n) time.
归并排序是稳定的，并且运行时间是 O(n log n)。

Because the dataset is huge and we need predictable performance, we chose mergesort over quicksort for the external sorting step.
由于数据集非常大且需要可预测的性能，我们在外部排序步骤中选择了归并排序而不是快速排序。

词源 Etymology

merge（合并）+ sort（排序）组成的复合词，字面意思是“通过合并来完成排序”。名称直接描述了算法的核心操作：把已排序的子序列归并成更大的有序序列。该术语在计算机科学算法教材中广泛使用。

相关词 Related Words

• Algorithm
• Divide-and-conquer
• Quicksort
• Heapsort
• Stable-sort
• Merge
• Sort

文学与著作中的用例 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，“CLRS”）：以归并排序作为分治法与递归分析的经典示例。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Donald E. Knuth）：讨论排序与查找的系统性著作中涵盖归并思想与相关技术。
• Algorithms（Robert Sedgewick & Kevin Wayne）：在比较排序章节中介绍归并排序及其实现细节与性能分析。
• Programming Pearls（Jon Bentley）：在性能与工程实践相关的讨论中常涉及排序选择与思路（包括归并类方法）。