多线程归并排序改进版

利用多线程归并有序集改进了下多线程排序，只剩下多线程拷贝没实现了。。。

代码

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