实现原理
今天介绍比前面三种排序算法性能更好的排序算法 —— 归并排序。
该算法是利用分治思想解决问题的一个非常典型的应用，归并排序的基本思路就是先把数组一分为二，然后分别把左右数组排好序，再将排好序的左右两个数组合并成一个新的数组，最后整个数组就是有序的了。
所谓归并排序，指的是如果要排序一个数据序列，我们可以先把该序列从中间分成前后两部分，然后对这两部分分别做排序操作，再将排好序的两部分合并在一起，这样整个数据序列就都有序了。
运用递归法实现归并操作的主要步骤:
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列。
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置。
- 比较两个指针所指向的元素，选择较小的元素放入到合并空间，并将指针移动到下一位置。
- 重复步骤3直到某一指针到达序列尾，然后将另一序列剩下的所有元素直接复制到合并序列尾。
归并排序使用了分治思想，分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。说到这里，可能你会联想起我们之前讲到的一个编程技巧 —— 递归，没错，归并排序就是通过递归来实现的。这个递归的公式是每次都将传入的待排序数据序列一分为二，直到变成不能继续分割的最小区间单元，然后将最小区间单元数据排序后合并起来，最终返回的就是排序好的数据序列了。图示如下：
动图演示
归并排序算法原理：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列.
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置.
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置.
- 重复上一步直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾.
示例代码
通过上面的分析，我们知道归并=递归+合并，对应的 Go 实现代码如下：
package main
import (
"fmt"
)
// 归并排序
func mergeSort(nums []int) []int {
if len(nums) <= 1 {
return nums
}
// 获取分区位置
p := len(nums) / 2
// 通过递归分区
left := mergeSort(nums[0:p])
right := mergeSort(nums[p:])
// 排序后合并
return merge(left, right)
}
// 排序合并
func merge(left []int, right []int) []int {
i, j := 0, 0
m, n := len(left), len(right)
// 用于存放结果集
var result []int
for {
// 任何一个区间遍历完，则退出
if i >= m || j >= n {
break
}
// 对所有区间数据进行排序
if left[i] <= right[j] {
result = append(result, left[i])
i++
} else {
result = append(result, right[j])
j++
}
}
// 如果左侧区间还没有遍历完，将剩余数据放到结果集
if i != m {
for ; i < m; i++ {
result = append(result, left[i])
}
}
// 如果右侧区间还没有遍历完，将剩余数据放到结果集
if j != n {
for ; j < n; j++ {
result = append(result, right[j])
}
}
// 返回排序后的结果集
return result
}
func main() {
nums := []int{4, 5, 6, 7, 8, 3, 2, 1}
sortedNums := mergeSort(nums)
fmt.Println(sortedNums)
}性能分析
最后我们来看下归并排序的性能：
- 归并最后到底都是相邻元素之间的比较交换，并不会发生相同元素的相对位置发生变化，故是稳定性算法；
- 时间复杂度是 O(nlogn)，要优于冒泡排序和插入排序的 O(n2)；
- 归并排序需要额外的空间存放排序数据，不是原地排序，最多需要和待排序数据序列同样大小的空间，所以空间复杂度是 O(n)。
归并排序的时间复杂度推导过程
归并的思路时将一个复杂的问题 a 递归拆解为子问题 b 和 c，再将子问题计算结果合并，最终得到问题的答案，这里我们将归并排序总的时间复杂度设为 T(n)，则 T(n) = 2*T(n/2) + n，其中 T(n/2) 是递归拆解的第一步对应子问题的时间复杂度，n 则是排序合并函数的时间复杂度（一个循环遍历），依次类推，我们可以推导 T(n) 的计算逻辑如下：
递归到最后，$T(n/2^k)≈T(1)$，也就是 $n/2^k = 1，$，计算归并排序的时间复杂度，就演变成了计算 k 的值，$2^k = n$，所以 $k=log_2n$，我们把 k 的值带入上述 T(n) 的推导公式，得到：T(n) = 2*T(n/2) + n = 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n = 4(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n = ... = 2^k*T(n/2^k) + k*n
注：上述公式中 2 是下标，即 $log_2n$。T(n) = n*T(1) + n*log2n = n(C + log2n)
把常量和低阶忽略，所以 $T(n) = nlogn$。优化改进
在规模较小时，合并排序可采用直接插入，避免递归调用； 在写法上，可以在生成辅助数组时，俩头小，中间大，这时不需要再在后边加俩个while循环进行判断，只需一次比完。 为了节省将元素复制到辅助数组作用的时间，可以在递归调用的每个层次交换原始数组与辅助数组的角色。总结
归并排序和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
