揭秘合并排序：分治排序初学者指南

归并排序由约翰·冯·诺依曼于 1945 年提出，主要是为了提高大型数据集的排序效率。冯·诺依曼的算法旨在使用分而治之的方法提供一致且可预测的排序过程。这种策略允许归并排序有效地处理小型和大型数据集，保证在所有情况下都能实现稳定的排序，时间复杂度为 O(n log n)。

归并排序采用分而治之方法，将数组分割成更小的子数组，对它们进行递归排序，然后将排序后的数组合并在一起。这种方法将问题分解为可管理的块，对每个块进行单独排序并有效地将它们组合起来。因此，通过划分排序工作量，该算法即使在大型数据集上也能表现良好。

递归是一个函数调用自身来解决同一问题的较小版本的过程。它不断分解问题，直到问题足够简单可以直接解决，这称为基本情况。

下面是 JavaScript 中归并排序的实现，展示了如何递归地拆分和合并数组：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

为了更好地理解归并排序的工作原理，让我们使用数组来演示整个过程：[38, 27, 43, 3, 9, 82, 10]

第 1 步：递归除法（mergeSort 函数）
该数组被递归地分割成更小的子数组，直到每个子数组只有一个元素。这是通过 mergeSort 函数中的以下几行实现的：

function mergeSort(arr) {
    if (arr.length <= 1) return arr;

这会停止我们的递归。

以下是递归除法的展开方式：

• 初始调用: mergeSort([38, 27, 43, 3, 9, 82, 10])
  • 数组在中点分割： [38,27,43] 和 [3,9,82,10]

• 上半场：

  • 合并排序([38,27,43])
    • 在中点分割：[38] 和 [27, 43]
  • 合并排序([27, 43])
    • 分为[27]和[43]
  • 子数组 [38]、[27] 和 [43] 现在是单独的元素，可以合并。

• 下半场：

  • 合并排序([3, 9, 82, 10])
    • 在中点分割：[3, 9] 和 [82, 10]
  • 合并排序([3, 9])
    • 分为[3]和[9]
  • 合并排序([82, 10])
    • 分为[82]和[10]
  • 子数组 [3]、[9]、[82] 和 [10] 现在已准备好合并。

第 2 步：合并已排序的子数组（合并函数）
现在，我们开始使用 merge 函数将子数组按排序顺序合并在一起：

function merge(left, right) {
    let result = [];
    while (left.length && right.length) {
        if (left[0] < right[0]) result.push(left.shift());
        else result.push(right.shift());
    }
    return result.concat(left, right);
}

合并过程的工作原理如下：

第一次合并（来自基本情况）：

• 合并 [27] 和 [43] → 结果为 [27, 43]
• 将 [38] 与 [27, 43] 合并 → 结果为 [27, 38, 43]

此时，数组的左半部分已完全合并：[27, 38, 43]。

第二次合并（来自基本情况）：

• 合并 [3] 和 [9] → 结果为 [3, 9]
• 合并 [82] 和 [10] → 结果为 [10, 82]
• 将 [3, 9] 与 [10, 82] 合并 → 结果为 [3, 9, 10, 82]

现在，右半部分已完全合并：[3, 9, 10, 82]。

第 3 步：最终合并
最后，使用 merge 函数将两半 [27, 38, 43] 和 [3, 9, 10, 82] 合并：

比较 27（左[0]）和 3（右[0]）。由于 3 比较 27 和 9。将结果加上 9。
比较 27 和 10。结果加 10。
比较 27 和 82。将结果加上 27。
比较 38 和 82。结果加上 38。
比较 43 和 82。将 43 添加到结果中。
添加右侧数组中剩余的元素 82。
完全合并和排序的数组是：
[3, 9, 10, 27, 38, 43, 82].

时间复杂度： 最佳、平均和最坏情况：O(n log n)
让我们仔细看看：

除法（O(log n)）：每次将数组分成两半，问题的大小就会减小。由于数组在每一步都被分成两半，因此执行此操作的次数与 log n 成正比。例如，如果有 8 个元素，则可以将它们分成两半 3 次（因为 log2(8) = 3）。

合并（O(n)）：划分数组后，算法将较小的数组按顺序合并在一起。合并两个大小为 n 的排序数组需要 O(n) 时间，因为您必须对每个元素进行比较和组合一次。

总体复杂度（O(n log n)）：由于除法需要 O(log n) 步骤，并且在每一步合并 n 个元素，因此总时间复杂度是这两者的乘积：O(n log n)。

空间复杂度： O(n)
合并排序需要与数组大小成正比的额外空间，因为它在合并阶段需要临时数组来存储元素。

与其他排序算法的比较：
快速排序：虽然快速排序的平均时间复杂度为 O(n log n)，但最坏的情况可能是 O(n^2)。合并排序避免了这种最坏的情况，但当空间受到关注时，快速排序对于内存中排序通常更快。
冒泡排序：比合并排序效率低得多，平均和最坏情况的时间复杂度为 O(n^2)。

真实世界用法
合并排序广泛用于外部排序，其中需要从磁盘对大型数据集进行排序，因为它可以有效地处理无法放入内存的数据。它也通常在并行计算环境中实现，其中子数组可以利用多核处理进行独立排序。

此外，Python (Timsort)、Java 和 C++ (std::stable_sort) 等库和语言都依赖归并排序的变体来确保排序操作的稳定性，使其特别适合对对象和复杂数据结构进行排序。

结论
由于其稳定性、一致的性能以及对大型数据集排序的适应性，合并排序仍然是理论计算机科学和实际应用中的基本算法。虽然 QuickSort 等其他算法在某些情况下可能执行得更快，但合并排序保证的 O(n log n) 时间复杂度和多功能性使其对于内存受限的环境以及维护具有相同键的元素的顺序非常有价值。它在现代编程库中的作用确保了它在现实世界的应用程序中保持相关性。

来源：

1. Knuth，Donald E. 计算机编程艺术，卷。 3：排序和搜索。 Addison-Wesley Professional，1997 年，第 158-160 页。
2. Cormen，Thomas H. 等人。算法简介。麻省理工学院出版社，2009 年，第 2 章（归并排序）、第 5 章（算法复杂性）、第 7 章（快速排序）。
3. Silberschatz、亚伯拉罕等人。数据库系统概念。 McGraw-Hill，2010 年，第 13 章（外部排序）。
4. “蒂姆索特。” Python 文档、Python 软件基础。 Python 的 Timsort
5. “Java 数组.排序”。 Oracle 文档。 Java 的 Arrays.sort()

以上是揭秘合并排序：分治排序初学者指南的详细内容。更多信息请关注PHP中文网其他相关文章！