利用多线程归并有序集改进了下多线程排序，只剩下多线程拷贝没实现了。。。
代码
package multisortex
func binsearch(x int, a []int) int {
var l, r = 0, len(a)
for l < r {
mid := (l + r) / 2
if a[mid] >= x {
r = mid
} else {
l = mid + 1
}
}
return l
}
func normmerge(a []int, b []int, c []int) {
var i, j, k = 0, 0, 0
for i < len(a) || j < len(b) {
if i < len(a) && j < len(b) {
if a[i] <= b[j] {
c[k] = a[i]
i++
} else {
c[k] = b[j]
j++
}
} else if i < len(a) {
c[k] = a[i]
i++
} else {
c[k] = b[j]
j++
}
k++
}
}
func pmerge(a []int, b []int, c []int, ch chan int, td int) {
if td == 1 {
normmerge(a, b, c)
} else if len(b) == 0 {
copy(c, a)
} else if len(a) == 0 {
copy(c, b)
} else {
var sed = make(chan int)
var mid = len(a) / 2
var pos = binsearch(a[mid], b)
c[mid+pos] = a[mid]
go pmerge(a[:mid], b[:pos], c[:mid+pos], sed, td>>1)
pmerge(a[mid+1:], b[pos:], c[mid+pos+1:], nil, td>>1)
<-sed
}
if ch != nil {
close(ch)
}
}
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 = j + 2*i
if k > n {
k = n
}
normmerge(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)
} else {
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
pmerge(arr[:mid], arr[mid:], buff, nil, level)
copy(arr, buff)
}
if sed != nil {
close(sed)
}
}
func MergeSort(arr []int, t int) {
buff := make([]int, len(arr))
mergesort(arr, buff, nil, t)
}
benchmark代码
package multisortex
import (
"math/rand"
"testing"
)
func BenchmarkT1(b *testing.B) {
b.N = 4
b.StopTimer()
n := 1 << 24
arr := make([]int, n)
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
for i := 0; i < n; i++ {
arr[i] = rand.Intn(n)
}
b.StartTimer()
MergeSort(arr, 1)
}
}
func BenchmarkT2(b *testing.B) {
b.N = 4
b.StopTimer()
n := 1 << 24
arr := make([]int, n)
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
for i := 0; i < n; i++ {
arr[i] = rand.Intn(n)
}
b.StartTimer()
MergeSort(arr, 2)
}
}
func BenchmarkT4(b *testing.B) {
b.N = 4
b.StopTimer()
n := 1 << 24
arr := make([]int, n)
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
for i := 0; i < n; i++ {
arr[i] = rand.Intn(n)
}
b.StartTimer()
MergeSort(arr, 4)
}
}
func BenchmarkT8(b *testing.B) {
b.N = 4
b.StopTimer()
n := 1 << 24
arr := make([]int, n)
b.StartTimer()
for i := 0; i < b.N; i++ {
b.StopTimer()
for i := 0; i < n; i++ {
arr[i] = rand.Intn(n)
}
b.StartTimer()
MergeSort(arr, 8)
}
}
测试结果
goos: windows
goarch: amd64
pkg: sort/multisortex
BenchmarkT1-4 4 2315135000 ns/op
BenchmarkT2-4 4 1271903875 ns/op
BenchmarkT4-4 4 1079014875 ns/op
BenchmarkT8-4 4 914900250 ns/op
PASS
ok sort/multisortex 30.314s
goos: windows
goarch: amd64
pkg: sort/multisort
BenchmarkT1-4 4 2367175725 ns/op
BenchmarkT2-4 4 1327192850 ns/op
BenchmarkT4-4 4 1212362200 ns/op
BenchmarkT8-4 4 1074262700 ns/op
PASS
ok sort/multisort 31.924s
