原理
1丶递归分解数组
2、合并数组
package main
import (
"fmt"
)
func main() {
arr := []int{4, 3, 9, 6}
sort(arr)
}
func sort(arr []int) {
temp := make([]int, len(arr))
sort2(arr, 0, len(arr)-1, temp)
fmt.Println(arr)
}
func sort2(arr []int, start int, end int, temp []int) {
if start < end {
middle := (start + end) / 2
sort2(arr, start, middle, temp)
sort2(arr, middle+1, end, temp)
merge(arr, start, middle, end, temp)
}
}
func merge(arr []int, start int, middle int, end int, temp []int) {
li := start
ri := middle + 1
i := 0
for li <= middle && ri <= end {
if arr[li] <= arr[ri] {
temp[i] = arr[li]
i++
li++
} else {
temp[i] = arr[ri]
i++
ri++
}
}
for li <= middle {
temp[i] = arr[li]
li++
i++
}
for ri <= end {
temp[i] = arr[ri]
ri++
i++
}
for j := 0; j < end-start+1; j++ {
arr[start+j] = temp[j]
}
}
