归并排序（MERGE-SORT）是利用归并的思想实现的排序方法。该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
具体来说，是将一个数组平分为两个子数组，将子数组再继续平分，以此往复，直到不可再分，此时子数组是有序的，无需排序。接下来将一个个子数组合并成一个有序的较大的子数组，依次往复最后得到一个完整的有序数组。
归并排序时间复杂度比较稳定，最好为 \(O(nlogn)\)，最差为 \(O(nlogn)\)，平均为 \(O(nlogn)\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 归并排序
func mergeSort(data []int) []int {
// 终止条件
if len(data) < 2 {
return data
}
// 递归划分
mid := len(data) / 2
// 归并左半部分
left := mergeSort(data[:mid])
// 归并右半部分
right := mergeSort(data[mid:])
// 合并left 和 right
var result []int
i, j := 0, 0
l, r := len(left), len(right)
for i < l && j < r {
if left[i] > right[j] {
// right[j]小，记录到结果中
result = append(result, right[j])
j++
} else {
// left[i]小，记录到结果中
result = append(result, left[i])
i++
}
}
// 此时 result 中是最小的数据，right[j:] 或 left[i:]有更大的数据
result = append(result, right[j:]...)
result = append(result, left[i:]...)
return result
}
func main() {
var l = []int{10, 15, 3, 6, 7, 12, 2}
fmt.Println("original,", l)
fmt.Println("asc result:", mergeSort(l))
}
输出：
1
2
original, [10 15 3 6 7 12 2]
asc result: [2 3 6 7 10 12 15]