多线程归并排序 go实现

特性

• 线程数可以调整
• 混合使用归并排序的递归版和非递归版实现减少递归调用损耗
• 线程利用率高
• 不足：归并排序的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)
}