# go 归并排序
归并排序也是分治的一种思路。
1. 将数组分为有序的两部分
2. 将有序的两个子数组合并为一个有序数组
## code
```go
package main
import "fmt"
func main () {
numbers := []int{5,1,9,2,6,3,9,4,1,6,3,7}
fmt.Printf("before arr is: %v\n", numbers)
res := mergeSort(numbers)
fmt.Printf("after arr is: %v\n", res)
}
// 返回一个有序切片
func mergeSort(arrs []int) []int {
n := len(arrs)
// 当切片只有一个元素的时候，那该切片就是有序的
if n < 2 {
return arrs
}
// 继续分治
mid := n / 2
left := arrs[:mid]
right := arrs[mid:]
return merge(mergeSort(left), mergeSort(right))
}
// merge将两个有序的数组合并成一个有序数组
func merge(left []int, right []int) []int {
res := make([]int, 0)
L_left := len(left)
L_right := len(right)
i, j := 0, 0
// 先取二者最优
for i < L_left && j < L_right {
if left[i] <= right[j] {
res = append(res, left[i])
i++
} else {
res = append(res, right[j])
j ++
}
}
// 补上剩下的尾巴
if i < L_left {
res = append(res, left[i:]...)
}
if j < L_right {
res = append(res, right[j:]...)
}
return res
}
```
## 结果展示
before arr is: [5 1 9 2 6 3 9 4 1 6 3 7]
after arr is: [1 1 2 3 3 4 5 6 6 7 9 9]
有疑问加站长微信联系（非本文作者））
