28.合并排序¶

Merge sort是最有效的排序算法之一。它的时间复杂度为O(n log n)，是所有通用排序算法中最快的一种。合并排序背后的理念是分割和征服--将一个大问题分解成几个较小的、较容易解决的问题，然后将这些解决方案合并成一个最终结果。合并排序的口号是：先分割，后合并。在本章中，你将从头开始实现合并排序。让我们从一个例子开始。

示例¶

假设你得到了一堆没有分类的扑克牌：

合并排序算法的工作原理如下。

首先，把这堆文件分成两半。你现在有两个未排序的堆：

现在，继续分割所得的牌堆，直到你不能再分割为止。最后，你将在每一堆中拥有一张（分类的！）牌：

最后，按照你分裂它们的相反顺序合并这些堆积物。在每次合并过程中，你都要把内容按分类顺序排列。这个过程很简单，因为每一堆都已经分类了：

实施¶

打开启动器的操场来开始。

分割¶

在操场的Sources文件夹中，创建一个名为MergeSort.swift的新文件。在该文件中写下以下内容：

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  let middle = array.count / 2
  let left = Array(array[..<middle])
  let right = Array(array[middle...])
  // ... more to come
}

这里，你把数组分成了两半。分割一次是不够的。然而，你必须不断地递归分割，直到你不能再分割为止，也就是每个细分部分只包含一个元素的时候。

要做到这一点，请更新mergeSort，如下所示：

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  // 1
  guard array.count > 1 else {
    return array
  }
  let middle = array.count / 2
  // 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  // ... more to come
}

你在这里做了两个改变：

递归需要一个base case，你也可以把它看作是一个"退出条件"。在这种情况下，基本情况是当数组只有一个元素时。
你现在在原数组的左右两半上调用mergeSort。只要你把数组分成两半，你就会尝试再次分割。

在你的代码编译之前，还有更多的工作要做。现在你已经完成了分割的部分，是时候集中精力进行合并了。

合并¶

你的最后一步是合并left和right数组。为了保持干净，你将为此创建一个单独的merge函数。

合并函数的唯一职责是接收两个sorted的数组，并在保留排序顺序的前提下将它们合并。在mergeSort函数的下面添加以下内容：

private func merge<Element>(_ left: [Element], _ right: [Element])
    -> [Element] where Element: Comparable {
  // 1
  var leftIndex = 0
  var rightIndex = 0
  // 2
  var result: [Element] = []
  // 3
  while leftIndex < left.count && rightIndex < right.count {
    let leftElement = left[leftIndex]
    let rightElement = right[rightIndex]
    // 4
    if leftElement < rightElement {
      result.append(leftElement)
      leftIndex += 1
    } else if leftElement > rightElement {
      result.append(rightElement)
      rightIndex += 1
    } else {
      result.append(leftElement)
      leftIndex += 1
      result.append(rightElement)
      rightIndex += 1
    }
  }
  // 5
  if leftIndex < left.count {
    result.append(contentsOf: left[leftIndex...])
  }
  if rightIndex < right.count {
    result.append(contentsOf: right[rightIndex...])
  }
  return result
}

以下是发生的情况：

leftIndex和rightIndex变量在你解析这两个数组时跟踪你的进度。
result数组将容纳合并后的数组。
从头开始，你依次比较left和right数组中的元素。如果你已经到了两个数组的末尾，就没有其他东西可以比较了。
两个元素中较小的元素进入result数组。如果这两个元素相等，就可以把它们都加起来。
第一个循环保证left或right是空的。由于两个数组都是排序的，这保证了剩下的元素大于或等于当前result中的元素。在这种情况下，你可以不通过比较来追加其余的元素。

结束了¶

通过调用merge来完成mergeSort函数。因为你是递归地调用mergeSort，所以算法会在合并之前对两半进行分割和排序。

public func mergeSort<Element>(_ array: [Element])
    -> [Element] where Element: Comparable {
  guard array.count > 1 else {
    return array
  }
  let middle = array.count / 2
  let left = mergeSort(Array(array[..<middle]))
  let right = mergeSort(Array(array[middle...]))
  return merge(left, right)
}

这段代码是合并排序算法的最终版本。下面是对合并排序的关键程序的总结：

合并排序的策略是分而治之，这样你就能解决许多小问题，而不是一个大问题。
它有两个核心职责：一个是递归地分割初始数组的方法，一个是合并两个数组的方法。
合并函数应该接收两个排序的数组并产生一个单一的排序数组。

最后--是时候看看这个动作了。回到主playground页面，用以下方法测试你的合并排序：

example(of: "merge sort") {
  let array = [7, 2, 6, 3, 9]
  print("Original: \(array)")
  print("Merge sorted: \(mergeSort(array))")
}

这个产出：

---Example of merge sort---
Original: [7, 2, 6, 3, 9]
Merge sorted: [2, 3, 6, 7, 9]

性能¶

合并排序的最佳、最差和平均时间复杂度是O(n log n)，这还不算太坏。如果你很难理解n log n是怎么来的，可以想想递归是怎么工作的。

一般来说，如果你有一个大小为n的数组，层数是log2(n)。当你递归时，你把一个数组分成两个更小的数组。这意味着一个大小为2的数组需要一个递归级别，一个大小为4的数组需要两个级别，一个大小为8的数组需要三个级别，以此类推。如果你有一个1,024个元素的数组，需要十级递归一分为二才能降到1024个单元素数组。
单个递归的成本是O(n)。一个递归级别将合并n个元素。如果有许多小的合并或一个大的合并，这并不重要；每一级合并的元素数量仍然是n。

这使得总成本为O(log n)×O(n)=O(n log n)。

前一章的排序算法是in-place的，使用swapAt来移动元素。相比之下，合并排序需要分配额外的内存来完成其工作。有多大？有log2(n)级的递归，在每一级，n个元素被使用。这使得总的空间复杂性为O(n log n)。合并排序是典型的排序算法之一。它相对简单易懂，可以作为分而治之算法工作原理的一个很好的介绍。合并排序是O(n log n)，而这个实现需要O(n log n)的空间。如果你能巧妙地记账，你可以通过丢弃没有被积极使用的内存，将所需的内存减少到O(n)。

关键点¶

合并排序属于divide-and-conquer的算法范畴。
有很多合并排序的实现，根据不同的实现，你可以有不同的性能特点。