三大排序算法之归并排序

在众多排序算法中，归并排序尤为出名。它基于著名的“分而治之”策略，将一个复杂问题拆分成多个较小的、更易解决的问题，然后将这些小问题的解合并以解决原始问题。

在本文中，我们探讨归并排序的实现细节，并估算其复杂度，使用 $O$ 符号表示。为了更好地理解，我们还通过示例来讲解。

一、归并排序算法

这个算法的主旨在于从原始数组的小子数组开始，递归地进行排序。当这些子数组排序完毕，它们会被合并成一个更大尺寸的新数组。这个过程一直进行，直至获得原始数组的排序版本。

初听可能觉得这方法过于复杂，但实际上，从已排序的数组中生成一个新的有序数组是一个相对快速的过程。

我们先来讨论合并函数。在理解了这个之后，我们将利用它来完成算法的最终形态。

二、归并函数

归并函数的作用是将两个已排序的子数组合并为一个新的有序数组，这个新数组包括了两个子数组中的所有元素。在下述代码片段中，我们传入一个元素数组，该数组由两个已排序的子数组 $array[left,middle]$ 和 $array[middle+1,right]$ 构成。

def merge(array: list, left: int, middle: int, right: int):
    i, j = left, middle + 1
    new_array = []
    while i <= middle and j <= right:
        if array[i] <= array[j]:
            new_array.append(array[i])
            i += 1
        else:
            new_array.append(array[j])
            j += 1
    while i <= middle:
        new_array.append(array[i])
        i += 1
    while j <= right:
        new_array.append(array[j])
        j += 1
    for i in range(left, right + 1):
        array[i] = new_array[i - left]

我们使用两个指针 i 和 j 来依次遍历这两个子数组的元素。在每次迭代中，我们比较 $array[i]$ 和 $array[j]$的元素，并将较小的元素加入到新数组 new_array 中。添加元素后，相应地增加指针 $i$ 或 $j$，使其指向下一元素。

这个循环过程一直持续到某个子数组的所有元素都被并入 new_array 中。接着，我们将另一个子数组中剩余的较大值元素全部加入 new_array。

最终，我们把排序后的 new_array 中的元素复制回原数组。这样，原数组中从索引 $left$到 $right$的部分就完成了排序。

需要注意的是，对于两个长度为 $N$的子数组，我们仅需线性时间遍历每个元素一次。因此，这个过程的时间复杂度为 $O(N)$。

三、示例

假定我们有一个数组 $array$，它包括两个已排序的子数组 $array[0:3]$和 $array\text{[}4:7]$。首先，我们初始化两个指针 $i$和 $j$，这两个指针分别指向这两个子数组中的最小元素。具体来说，指针 $i$ 指向索引为 $0$ 的元素，指针 $j$ 指向索引为 $4$ 的元素。

• 第1次迭代：比较 $array[0]=2$ 和 $array[4]=3$。由于 $2\le 3$，我们将 2 作为新数组的第一个元素，并将 $i$ 加 1，让它指向下一个元素 9。
• 第2次迭代：比较 $array[1]=9$ 和 $array[4]=3$。由于 $9>3$，我们将 3 作为新数组的第二个元素，并将 $j$ 加 1，让它指向下一个元素 7。
• 第3次迭代：比较$array[1]=9$ 和 $array[5]=7$。由于 $9>7$，我们将 7 作为新数组的下一个元素，并将 $j$ 加 1。

…

• 第7次迭代：此时 $j$ 指向右侧子数组的末尾，表示左侧子数组中从索引 $i$ 开始的所有元素均大于右侧子数组中的任何元素。因此，我们将右侧子数组中剩余的元素（16 和 20）复制到新数组中。

这个过程完成后，新数组中的所有有序值将被复制回原始数组。

四、排序方法

排序函数通过递归方式调用自己，分别对其左半部和右半部进行排序。当这两部分都被排序后，它们将在调用 $merge\_sort()$ 函数之后被合并在一起。

def merge_sort(array: list, left: int, right: int):
    if left < right:
        middle = (left + right) // 2
        merge_sort(array, left, middle)
        merge_sort(array, middle + 1, right)
        merge(array, left, middle, right)

为了让函数接口对客户端更友好，我们可以将 $merge\_sort()$ 的首次调用包装在另一个函数内。这样做的好处是客户端不必传递左右参数，从而有效地遵循了封装设计原则。

def sort(array: list) -> list:
    merge_sort(array, 0, len(array) - 1)

五、示例

下面的图示展示了一个含有 8 个元素的数组进行归并排序的调用层级。首先，我们把数组分割成两个长度各为 4 的部分。对于每一半，我们再次进行归并排序，这将产生长度为 2 的数组。此外，不需要再分割这些数组，因为任何只含一个元素的数组自然而然就是有序的。

我们按照算法继续对长度为 2 的数组进行排序。每当两个相邻的长度为 2 的数组完成排序后，它们就会合并成一个长度为 4 的有序数组。这一过程对所有长度为 2 的数组都会执行。接着，当两个相邻的长度为 4 的数组都排序完毕时，它们会以类似的方式合并成一个长度为 8 的有序数组。

这个程序将一直进行，直到所有的元素都排列有序为止。

六、复杂度分析

为了评估复杂度，我们需要先了解递归调用的结构。设我们有一个大小为 $N$ 的数组待排序。

我们先将这个数组分为两个大小各为 $N/2$ 的子数组。接着，每个子数组再分为两个大小为 $N/4$ 的更小子数组。如此一来，我们得到四个大小为 $N/4$的数组。依此类推，下一层我们将得到八个大小为 $N/8$ 的数组。我们重复这个过程，直到分割出 $N$ 个大小为 1 的数组。这个过程在下图中有所示意。

对于图中显示的每个数组，我们需要执行一次归并操作，该操作的时间复杂度为 $O(K)$，其中 $K$ 是数组的长度。现在让我们来计算上图中每一层级数组的总时间复杂度。

• 第一层级，我们有一个大小为 N$的数组，需要$O(N)$的处理时间。
• 第二层级，有两个大小为 $N/2$ 的数组。每个数组需要 $O(N/2)$的时间，总时间是 $2\ast O(N/2)=O(N)$。
• 第三层级，有四个大小为 $N/4$ 的数组。每个数组需要 $O(N/4)$的时间，总时间是 $4\ast O(N/4)=O(N)$。
• 最后一层级包含 $N$ 个大小为 1 的数组。每个数组需要 $O(1)$ 的时间，总时间是 $N\ast O(1)=O(N)$。

按照这种逻辑，每一层级的处理时间都是$O(N)$。因为每一步骤中数组都被分成两半，很容易发现总共有 $O(logN)$ 层级。这导致最终的时间复杂度为 $O(N)\ast O(logN)=O(N\ast logN)$。

七、优点

• 高效性。归并排序的总体时间复杂度为 $O(N\ast logN)$，这是所有基于元素比较的排序算法中可达到的最优复杂度。但是，在归并过程中，元素需暂时在另一个数组中排序，该数组的大小等于两个子数组的总长度，因此其空间复杂度为 $O(N)$。
• 简易性。相较于其他高效的排序算法，归并排序更易于理解和实现。
• 稳定性。当初始数组中有相等元素时，归并排序不会改变它们的相对顺序。这一特性对于实现过程中包含排序的更复杂算法来说非常重要。

八、结论

归并排序是一种广泛使用的排序算法，它使我们深入理解了分治策略的核心原理。归并排序以其独特的优势，如算法结构清晰、时间复杂度低$O(N\ast logN)$，以及稳定的排序性能，成为了众多领域首选的排序方法。它的实现既展示了算法设计的简洁性，也体现了在处理大规模数据时的高效性和可靠性。