多线程合并有序集

在归并排序中，有个合并有序集操作。之前在用多线程实现归并排序中，并没将合并操作多线程化，导致并行度只有log(n) (虽然已经很大了)，但算导上提供有相关的算法，最近就学了下，顺便用golang实现了下

一般的实现方式

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 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 merge(a []int, b []int, c []int) {
    if len(b) == 0 {
        copy(c, a)
        return
    }
    if len(a) == 0 {
        copy(c, b)
        return
    }
    var mid = len(a) / 2
    var pos = binsearch(a[mid], b)
    c[mid+pos] = a[mid]
    merge(a[:mid], b[:pos], c[:mid+pos])
    merge(a[mid+1:], b[pos:], c[mid+pos+1:])
}

性能评估 复杂度是O(N)的，虽然里面有个二分查找，但分治后的长度在不断减小可以忽略不计.但递归对性能有损耗是非递归版的2倍

多线程版

func pmerge(a []int, b []int, c []int, ch chan int, td int) {
    if td == 1 {
        normmerge(a, b, c)
        close(ch)
        return
    }
    if len(b) == 0 {
        copy(c, a)
        close(ch)
        return
    }
    if len(a) == 0 {
        copy(c, b)
        close(ch)
        return
    }
    var ch1 = make(chan int)
    var ch2 = 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], ch1, td>>1)
    go pmerge(a[mid+1:], b[pos:], c[mid+pos+1:], ch2, td>>1)
    <-ch1
    <-ch2
    close(ch)
}
func pMerge(a []int, b []int, c []int, td int) {
    var ch = make(chan int)
    pmerge(a, b, c, ch, td)
    <-ch
}

性能评估：肯定比单线程快，而且分治到一定程度后用的是单线程非递归版算法，不用递归二分查找，提高性能。但线程调度算法有点问题，看数据特性，如果设置可用线程为8，最少使用线程为3，最多自然全部使用