分治法
归并排序是分治法的一种应用，分治法的核心思想是“分而治之”，就是把一个问题分化成若干个子可以用相同的方法去解决的小问题，再把子问题一层一层继续分化成粒度更小的子问题，直到最小单元的子问题可以很容易得到解，再把得到的解逐级合并为根问题的解。
分治法主要分为三个步骤：
- 分解：将根问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。
- 解决：如果子问题是可以直接被解决的，就直接解决并返回，如果是无法解决的，就继续分解成粒度更小的子问题。
- 合并：将各个子问题的解合并为原问题的解。
归并排序
归并排序的核心思想还是蛮简单的。如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。
归并排序就是利用分治法的思想，主要分为拆和合两个阶段：
- 拆：把要排序的长度为n数组从中间开始拆分为长度为n/2的数组，然后把n/2长度的数组继续递归拆分为长度为1的子序列，最终就是长度为n的数组被拆分为n个长度为1的子序列。因为子序列的长度是1可以理解它就是有序的。
- 合：拆分完的子序列两两合并为有序列的粒度更大的子序列，经过逐级归并最终得到原数组的排序结果
代码实现
首先是拆分的过程，使用递归的方法将数组逐级拆分为长度为1的数组
func mergeSort(arr []int,start ,end int) {
if start >= end {
return
}
mid := (start+end)/2
//从中间位置拆分数组
mergeSort(arr,start,mid)
mergeSort(arr,mid + 1,end)
//将拆分后的数组进行合并
merge(arr,start,mid,end)
}
合并函数签名 func merge(arr []int,start,mid,end int)，这里的arr是原数组，而要合并的也就是arr[start,mid]、arr[mid+1,end]这两个已经排序过的子序列。merge最终将这两个子序列合并成一个有序数组然后替换为原数组start和end中间的元素。
具体代码里声明了一个tmp用于存储左侧元素和右侧元素的排序结果。从左右两测子序列的头部偏移量为0开始遍历比较，取最小的元素放入tmp中并且将这个子序列的偏移量+1。直到其中一个子序列的元素都被放在了tmp中，就可以把另一个子序列的剩余元素直接放入tmp中。
func merge(arr []int,start,mid,end int){
rightIndex := start
leftIndex := mid + 1
tmpIndex := 0
tmp := make([]int,1 + end - start)
//取两个子序列较小元素放入tmp
for rightIndex <= mid && leftIndex <= end {
if arr[rightIndex] <= arr[leftIndex] {
tmp[tmpIndex] = arr[rightIndex]
tmpIndex++
rightIndex++
}else {
tmp[tmpIndex] = arr[leftIndex]
tmpIndex++
leftIndex++
}
}
//判断是哪边的序列还有剩余元素
var appendStart,appendEnd int
if rightIndex > mid {
appendStart = leftIndex
appendEnd = end
}else {
appendStart = rightIndex
appendEnd = mid
}
//将剩余元素放入tmp
for appendStart <= appendEnd {
tmp[tmpIndex] = arr[appendStart]
tmpIndex++
appendStart++
}
//将tmp中元素放入原数组
for k,v :=range tmp{
arr[start + k] = v
}
}
测试代码：
func main() {
arr := []int{1,2,3,1,5,3,2,1,4,6,9,7}
mergeSort(arr,0,len(arr)-1)
fmt.Println(arr)
}
还有一种merge的方法是通过将两个序列分为两个数组，然后分别在这两个数组最后加上一个作为辅助的“哨兵”，这样遍历完一个数组的时候会因为这个辅助的哨兵过大而阻塞等待另外一个数组的遍历，省去了判断剩余元素的步骤。（因为slice的深拷贝，代码其实也并不简略）
func sentryMerge(arr []int,start,mid,end int){
rightArr,leftArr := make([]int,len(arr[start:mid+1]) +1 ),make([]int,len(arr[mid+1:end+1]) +1 )
copy(rightArr,arr[start:mid+1])
copy(leftArr,arr[mid+1:end+1])
rightArr[len(rightArr)-1],leftArr[len(leftArr)-1] = math.MaxInt32,math.MaxInt32
var rightIndex,leftIndex int
tmp := make([]int,1 + end - start)
for k,_ := range tmp {
if rightArr[rightIndex] <= leftArr[leftIndex] {
tmp[k] = rightArr[rightIndex]
rightIndex++
}else {
tmp[k] = leftArr[leftIndex]
leftIndex++
}
}
//将tmp中元素放入原数组
for k,v :=range tmp{
arr[start + k] = v
}
}
归并排序的优劣
归并排序的时间复杂度非常稳定在任何情况都是O(nlogn)，单从时间复杂度来考虑的话是一种非常优秀的排序方法，但是归并排序的空间复杂度却不像插入排序、快速排序一样，它的空间复杂度是O(n)，所以在应用上并不是非常广泛。