特性
- 线程数可以调整
- 混合使用归并排序的递归版和非递归版实现减少递归调用损耗
- 线程利用率高
- 不足：归并排序的merge部分，任务无法分摊，没有充分利用
1000万的随机数
-
递归版时间
real 0m3.037s user 0m2.859s sys 0m0.125s -
单线程
BenchmarkT1-4 10 2718827530 ns/op 268435456 B/op 2 allocs/op -
双线程
BenchmarkT2-4 10 1783577760 ns/op 268435792 B/op 4 allocs/op -
四线程
BenchmarkT4-4 10 1692288480 ns/op 268436278 B/op 7 allocs/op
代码
package main
func merge(x, y, out []int) {
n, m := len(x), len(y)
for i, j, k := 0, 0, 0; k < n+m; k++ {
if i < n && j < m {
if x[i] < y[j] {
out[k] = x[i]
i++
} else {
out[k] = y[j]
j++
}
} else {
if i < n {
out[k] = x[i]
i++
} else {
out[k] = y[j]
j++
}
}
}
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
func mergesortT(arr, buff []int) {
n := len(arr)
x, y := arr, buff
i, j, k := 0, 0, 0
for i = 1; i < n; i <<= 1 {
for j = 0; j < n-i; j = k {
k = min(n, j+2*i)
merge(x[j:j+i], x[j+i:k], y[j:k])
}
x, y = y, x
}
if &x[0] != &arr[0] {
copy(arr, x)
}
}
func mergesort(arr, buff []int, sed chan int, level int) {
n := len(arr)
if n <= 2 || level <= 1 {
mergesortT(arr, buff)
if sed != nil {
sed <- 0
}
return
}
recv := make(chan int)
mid := n >> 1
go mergesort(arr[:mid], buff[0:mid], recv, level>>1)
mergesort(arr[mid:], buff[mid:], nil, level>>1)
<-recv
merge(arr[:mid], arr[mid:], buff)
copy(arr, buff)
if sed != nil {
sed <- 0
}
}
func MergeSort(arr []int, t int) {
buff := make([]int, len(arr))
mergesort(arr, buff, nil, t)
}
