声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流
归并排序算法的目的：将一个数组按照从小到大或者从大到小排序
归并排序算法于1945年由John von Neumann发明，在各种情况下，它的运算性能均为O(nlogn)。
归并排序的主要核心思想是分而治之：将一个很大的问题分解为几个小的问题，然后将这些小问题解决，从而等同于解决了这个大问题。
假设你有一个含n个数的数组，你需要将它们按照一定顺序整理起来。归并排序算法将会按照以下过程处理：
1.将所有数字放在一起，没有任何规律，比如排成一个横排。
2.将这一横排的数据从中间分开，变成两个横排，均未整理。
3.继续重复步骤2，直到无法再拆分。
4.将分开的小横排按照顺序两两合并在一起，形成排序好的数组。每一次合并，都是得到排序好的新数组。
举例
拆分
有一个未整理的数组为[2, 1, 5, 4, 9]。我们将这个数组拆分到无法继续拆分为止。
首先，我们可以将该数组拆分为[2, 1]和[5, 4, 9]。这两个数组还可以继续拆分么？显而易见，可以的！
我们继续将[2, 1]拆分为[1]和[2]。该数组无法继续拆分。而[5, 4, 9]可以拆分为[5]和[4, 9]，然后[4, 9]继续拆分为[4]和[9]。
所以，在拆分结束时，我们得到[2]，[1]，[5]，[4]，[9]。其实，最后得到的每个数组都只含有一个数字。
合并
拆分完数组之后，我们需要将这些小数组进行有序合并。记住，我们的目的是将一个大的问题拆分成几个小问题来解决。每一次合并的时候，我们只会关心将要合并的两个数组，其它的数组暂不考虑。
拆分的时候，我们得到的数组是[2]，[1]，[5]，[4]，[9]，在第一次合并的时候，我们会得到[1, 2]，[4, 5]和[9]。因为这里的[9]是最后一个数组，没有多余的数组可以在这一次合并的时候跟它合并，所以轮空。
第二次合并，我们得到[1, 2, 4, 5]和[9]，由于[9]依然是最后一个数组，没有多余数组，继续轮空。
第三次合并，由于我们只剩下两个数组，我们得到[1, 2, 4, 5, 9]，排序结束。
从上向下执行
在Swift中，归并排序算法代码如下：
func mergeSort(_ array: [Int]) -> [Int] {
guard array.count > 1 else { return array } // 1
let middleIndex = array.count / 2 // 2
let leftArray = mergeSort(Array(array[0..<middleIndex])) // 3
let rightArray = mergeSort(Array(array[middleIndex..<array.count])) // 4
return merge(leftPile: leftArray, rightPile: rightArray) // 5
}
代码解析：
1.如果传入数组为空或者只有一个元素，我们就不需要继续拆分，直接返回该传入数组。
2.找出数组个数中间值。
3.使用步骤2得到的中间值，不断的拆分左边的数组。
4.同时不断拆分右边的数组。
5.最后，将所有数组合并到一起，得到排序数组。
合并过程代码如下：
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] {
// 1
var leftIndex = 0
var rightIndex = 0
// 2
var orderedPile = [Int]()
// 3
while leftIndex < leftPile.count && rightIndex < rightPile.count {
if leftPile[leftIndex] < rightPile[rightIndex] {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
} else if leftPile[leftIndex] > rightPile[rightIndex] {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
} else {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
}
// 4
while leftIndex < leftPile.count {
orderedPile.append(leftPile[leftIndex])
leftIndex += 1
}
while rightIndex < rightPile.count {
orderedPile.append(rightPile[rightIndex])
rightIndex += 1
}
return orderedPile
}
上述代码看起来貌似很复杂，但其实很直接：
1.在合并过程中，你需要创建2个索引来追踪合并的两个数组。
2.这里的空数组为合并数组，在接下来的步骤里，这个空数组会不断地从其它数组放入新元素。
3.这里的while循环会将左右两侧的数组进行比较，并按照大小放入到orderedPile里。
4.如果执行到步骤4，则证明leftPile和rightPile里的数字均已完全合并到orderedPile里。这时候，我们不需要继续做比较，只需要将剩下的数组合并起来。
这里我们举一个简单的例子来说明merge()的运行过程。假设我们有leftPile = [1, 7, 8]和rightPile = [3, 6, 9]。注意这里每一个数组都是已经整理好顺序的，在归并排序算法里，这个是必要条件。我们按照下图步骤将这两个数组合并到一起：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ ]
l r
左侧的索引l，右侧为r，当前左侧索引对应的数值为1，右侧索引对应的数值为3，因此，orderedPile添加进去的第一个数字为1。我们将l向右移动一个位置。
现在左侧索引对应的数字为7，右侧为3，因此，第二个放入的数字为3，右侧索引向右移动一个位置：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3 ]
l -->r
不断重复上述过程。在每一次过程中，我们都会从左侧或者右侧数组中拿出一个数字加入orderPile：
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6 ]
l -->r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7 ]
-->l r
leftPile rightPile orderedPile
[ 1, 7, 8 ] [ 3, 6, 9 ] [ 1, 3, 6, 7, 8 ]
-->l r
现在左侧数组已经为空，我们只需要将右侧数组剩下的数值直接加入orderPile，排序完成。我们得到[1, 3, 6, 7, 8, 9]。
这个算法其实很简单：在两个数组中，每次各取出一个数字进行比较，将最小的数字放入整理好的数组里，重复过程直到结束。当然，要注意前提是这两个数组都是排序好的数组。
从下向上执行
前一部分我们描述了归并算法里是由上向下的执行方法，因为该方法是先将数组拆分为小数组，然后再合并。其实，在整理过程中，我们可以跳过拆分过程，直接从合并数组开始。这种方法称作从下向上。
代码如下:
func mergeSortBottomUp<T>(_ a: [T], _ isOrderedBefore: (T, T) -> Bool) -> [T] {
let arrayCount = a.count
var arrayMatrix = [a, a] // 1
var sortedArrayIndex = 0
var width = 1
while width < arrayCount { // 2
var i = 0
while i < arrayCount { // 3
var j = i
var l = i
var r = i + width
let lmax = min(l + width, n)
let rmax = min(r + width, n)
while l < lmax && r < rmax { // 4
if isOrderedBefore(z[d][l], z[d][r]) {
z[1 - d][j] = z[d][l]
l += 1
} else {
z[1 - d][j] = z[d][r]
r += 1
}
j += 1
}
while l < lmax {
z[1 - d][j] = z[d][l]
j += 1
l += 1
}
while r < rmax {
z[1 - d][j] = z[d][r]
j += 1
r += 1
}
i += width*2
}
width *= 2
d = 1 - d // 5
}
return z[d]
}
要点：
1.我们在合并左右两侧的数组时候，不能同时修改它们自身数组的内容，所以我们需要一个临时工作数组来执行这个功能。但是每一次合并过程都重新分配新的临时工作数组是非常浪费资源的，因此，我们使用两个工作数组来代替，并用d来区分它们，数组z[d]是用来读取，z[d-1]用来写，我们称之为双重缓冲。
2.从概念上来说，这一版本的工作方式和上一个版本的工作方式是相同的。首先，它会合并长度为1的数组，然后是2，然后是4，以此类推。数组的长度是有width决定的。最初的时候它的数值是1，然后在每个循环结束后乘以2。所以外循环决定了需要合并的数组长度，在每一次进入新的循环，需要合并的数组的长度跟着变得更大。
3.内循环是一个合并过程，合并后的数组会被放入z[1 - d]。
4.从逻辑上来说，此版本与上一个版本相同，唯一不同的是，这里我们使用了双重缓冲，所以我们从z[d]上读数值，在z[1-d]写数组。这里的isOrderedBefore函数可以对比各种类型的数据，不仅仅是数字。
此函数为通用函数，我们可以对各种类型的数据进行排序。可以在playground进行测试：
let array = [2, 1, 5, 4, 9]
mergeSortBottomUp(array, <) // [1, 2, 4, 5, 9]
性能分析
归类排序算法的速度取决于数组的大小。数组越大，它需要执行的时间越久。原始数组是否排序好与速度无关，因为无论是否排序，归类排序都需要先将数组拆分，然后再合并。因此，归类排序算法的时间复杂度永远为O(nlogn)
对于归类排序算法来说，它的缺点就是在排序过程中，需要创建一个大小与被排序数组相同的工作数组，这个与就地排序类型的算法不一样，比如说快速排序算法。
在绝大多数情况下，归类排序算法能得到一个稳定的有序数列。也就是说，在排序对比的依据相同的情况下，该序列的顺序是稳定的。这种特性对数字或者字符排序来说并无特别之处，但是在排序复杂对象的时候，效果显著。
网友评论