1600万的整数排序pingcap-talent-plan(1)

Merge Sort

问题描述

Go 语言实现一个16M的整数(int64)多路归并的数组排序

思路

将待排序数组分成多个组，利用多个goroutine实现各个组的并行排序；然后通过Heap(最小堆)进行多路归并排序；

实现

实现一个协程池实现任务的并行处理，将待排序切片分组并封装成SortTask放入协程池
运行，待全部执行完成后ConcurrentSorter收集排序结果，并封装成MergeTask放入协程池中进行合并。

协程池pool.go
- 配置最大协程数量
- 按需创建协程
- 空闲超时则回收协程
合并有序切片algorithm.heap_merge.go
若采用2路循环合并，每次合并需要申请长度为2路之和的内存保存合并结果，循环合并会导致过多的内存申请。通过堆实现多路的有序切片的合并，只需要额外申请一次一倍的内存用于存放合并结果。

归并算法

输入：n路待合并的有序slice
输出：有序slice

堆node定义为一个SortedSlice，实现了hasNext函数，用于迭代到当前slice的下一个元素；

type Iterator struct {
    slice []int64
    index int
}

func (i *Iterator) HasNext() bool {
    return i.index < len(i.slice)-1
}

func (i *Iterator) Next() {
    i.index++
}

func (i *Iterator) Value() int64 {
    return i.slice[i.index]
}

type SortedSlice struct {
    slice []int64
    Iterator
}

堆的定义：

type HeapMerge struct {
    nodes []*SortedSlice
}

构建一个n个元素的最小堆
从每路slice中取首个元素组成数组，调整堆；每次从堆顶，取一个元素，放入合并后的slice中
- 如果hasNext=true，执行当前node的Next()，重新调整当前的原因
- 如果hasNext=false, 当前slice已经空了，因此剔除堆顶, 然后需要重建堆，原因是堆中的父子关系已经破坏。

if h.nodes[0].HasNext() {
    h.nodes[0].Next() //不需要获取值
    h.adjust(0, len(h.nodes))
} else { // 顶部的node(slice)已经为空
    if len(h.nodes) >= 1 {
        // 移除为已经合并完成的slice
        h.nodes = h.nodes[1:]
        //h.adjust(0, len(h.nodes))
        h.Build()
    } else {
        return 0, errors.New("merge complete")
    }
}