归并排序

发表于 更新于 分类于

参考：https://zhuanlan.zhihu.com/p/124356219

时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定

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(arr []int) {
temp := make([]int, len(arr))
mergeRecursive(arr, temp, 0, len(arr) - 1)
}

//归并排序
func mergeRecursive(arr []int, result []int, start, end int) {
if start >= end {
return
}
end1 := (end-start)>>1 + start
start1, start2 := start, end1 + 1
mergeRecursive(arr, result, start1, end1)
mergeRecursive(arr, result, start2, end)
k := start
for ; start1 <= end1 && start2 <= end; {
if arr[start1] < arr[start2] {
result[k] = arr[start1]
start1++
} else {
result[k] = arr[start2]
start2++
}
k++
}
for ; start1 <= end1; {
result[k] = arr[start1]
start1++
k++
}
for ; start2 <= end; {
result[k] = arr[start2]
start2++
k++
}
for k = start; k <= end; k++ {
arr[k] = result[k]
}
}