归并排序（Merge Sort）

归并排序是最高效的排序算法之一。该排序算法的时间复杂度是O(log n)，归并排序是由分割和合并组成的。将一个比较大的问题分割成若干容易解决的小问题，然后进行合并，得到一个最终的结果。归并排序的口诀就是先分割，后合并。

举个例子，假定你手中有如下一摞卡牌：

mergeSort1.png

排序算法的排序过程大致是这样的：
1，首先，将这一摞牌分成两半，这样就得到了两摞无序的卡牌。

mergeSort2.png
1，现在继续对每摞卡牌进行分割，直到不能在分割为止，到最后在每摞卡牌中，就只存在一张卡牌。
mergeSort3.png

1，最后，以和分割相反的顺序，将每一摞卡牌合并。在每一次合并的过程中，将数据按照规则进行排序。由于每一小摞的卡牌都已经有序，在合并的时候会比较容易些。

mergeSort4.png

实现

分割

首先，先将数组分成两半：

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
}

这里有两个变动点：
1，对函数进行了递归调用，在数组中有且只有一个元素时，停止递归调用。
2，对原数组的左右子数组都调用 mergeSort。

如上代码在能通过编译之前，仍然还有很多事情去做。现在已经完成了数组分割部分，是时候去关注于合并了。

合并

合并左右子数组是该算法的最后一步。为了更算法更明了一些，单独创建一个 merge 方法。

merge 方法的职责仅仅是 将两个将两个有序的数组合并成一个有序的数组。在 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
}

• 1，leftIndex 和 rightIndex 变量记录着遍历两个数组的进度。

• 2，resultArray 是最终排过序的数组。

• 3，从开头依次比较左右数组的元素，如果已经到达任意一个数组的末端，就没有元素去比较了。

• 4，比较两个元素，将比较小的元素放入resultArray，如果两个元素相等，把他俩都加入到数组中。

• 5，第一个循环保证了左数组或者右数组有一个已经添加完，由于数组都是有序的，这就保证了，数组中遗留的元素都是大于等于 result 里面的元素。

最后附上本文的相关代码DataAndAlgorim

参考链接《Data Structures & Algorithms in Swift》