归并排序

归并排序是一种基于分治算法的排序技术。它是最流行的排序算法之一，也是“分而治之”算法的最佳示例之一。

归并排序的工作原理：

归并排序通过将数组重复地分成两半来工作。直到它们不能再分为止（即，每个子数组只包含一个元素）。然后，当我们拥有这些琐碎的已排序列表（长度为1的列表）时，我们迭代地合并这些子列表，以产生最终的排序列表。

让我们更详细地看看归并排序是如何工作的：

• 找到中间点将数组分成两半：

中间点 \(mid\) = \(\lfloor(l + r) / 2\rfloor\)

• 递归调用归并排序：

对左半部分 \(mid\) 进行第一次调用，对右半部分 \(mid + 1\) 进行第二次调用。

• 合并步骤： 最后，调用合并函数，该函数选取两个已排序的子数组并进行合并以创建一个已排序的数组。

def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # 创建临时数组
    L = [0] * (n1)
    R = [0] * (n2)

    # 拷贝数据到临时数组 L[] 和 R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    # 合并临时数组回 arr[l..r]
    i = 0     # 初始第一个子数组的索引
    j = 0     # 初始第二个子数组的索引
    k = l     # 初始合并子数组的索引

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # 拷贝 L[] 的剩余元素，如果有的话
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # 拷贝 R[] 的剩余元素，如果有的话
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

def mergeSort(arr, l, r):
    if l < r:
        # 等同于 (l+r)//2，但避免了溢出大 l 和 h 的情况
        m = l+(r-l)//2

        # 递归排序两半
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)

为了更直观地理解这一点，我们可以想象以下过程：

假设我们要排序数组：[38, 27, 43, 3, 9, 82, 10]。

• 划分：

首先，我们将数组分成两半：INLINECODEf0d655f8 和 INLINECODE4c57ee2d。

然后，我们继续将这些数组分成两半，直到所有子数组都只包含一个元素。

在这一点上，数组被划分成了单个元素，我们可以认为它们已经是有序的了。

• 合并：

现在，我们开始从底部向上合并。

我们从两个单个元素开始，比如 INLINECODEe80e1ad7 和 INLINECODE50905b10。将它们合并得到 [27, 38]。

接下来，我们合并 INLINECODE0ed30750 和 INLINECODE8fca00dc 得到 [3, 43]。

然后，我们将 INLINECODEd5d65459 和 INLINECODE714cd689 合并得到 [3, 27, 38, 43]。

同样地，我们将右半部分 INLINECODE3a44f16c 中的单个元素合并并排序，最终得到 INLINECODE4b52e618。

最后，我们合并这两个已排序的子数组 INLINECODE52482edb 和 INLINECODEedfb1705，以得到最终的排序列表 [3, 9, 10, 27, 38, 43, 82]。

让我们分析一下合并函数。在合并过程中，我们首先比较 INLINECODE20cb10f0 和 INLINECODE02045e5c。只有当 INLINECODEe04133be 时，我们才将 INLINECODE5a814aec 放入结果数组，并将 i 加 1。这意味着当元素相等时，我们优先选择左半部分（前半部分）的元素。由于左半部分的元素在原数组中本来就在前面，所以我们保持了它们的相对顺序。因此，归并排序是一个稳定的排序算法。

复杂度分析

• 时间复杂度：

归并排序在最坏、平均和最好的情况下，时间复杂度都是 \(O(n \log n)\)。这是因为无论输入的初始状态如何，算法总是将数组递归地分成两半（\(\log n\) 层），并且在每一层上进行线性时间的合并操作（\(O(n)\)）。

然而，合并操作需要额外的 \(O(n)\) 空间来存储临时数组。

• 空间复杂度：

归并排序的空间复杂度为 \(O(n)\)。我们需要额外的空间来存储临时的子数组。

• 外部排序： 归并排序非常适合处理海量数据，尤其是当数据太大无法一次性装入内存时。我们可以利用归并排序将数据分块排序后存储在磁盘上，最后再合并这些有序的文件。
• 自定义比较： 它可以轻松地适应不同的比较规则，例如用于对对象进行排序，而不仅仅是简单的整数。
• 求逆序数： 我们可以修改归并排序的合并步骤来高效地计算数组中的逆序对数量，这在某些算法问题中非常有用。

常见问题 (FAQ)

问：归并排序总是比快速排序好吗？

答：不一定。虽然归并排序有稳定的 \(O(n \log n)\) 时间复杂度，但快速排序通常在实践中更快，因为它具有更好的局部性，可以更有效地利用缓存。此外，归并排序需要 \(O(n)\) 的额外空间，而原地排序版本的快速排序只需要 \(O(\log n)\) 的栈空间。

问：为什么归并排序的空间复杂度是 \(O(n)\)？

答：因为在合并两个子数组时，我们需要一个额外的辅助数组来暂时存储合并后的结果。这个辅助数组的大小与原数组成线性关系。

问：归并排序是原地算法吗？

答：标准实现中的归并排序不是原地算法，因为它需要与输入数组大小成比例的额外空间。不过，也存在一些高级的原地归并排序算法，但它们通常非常复杂且常数因子较大，不如标准版本实用。