第一周是给定了函数签名实现多路归并排序。这里。
为啥要考这个问题呢？个人认为多路归并在分布式数据库、分布式搜索引擎领域是挺常见的算法。用我相对熟悉的 es 来举例，在搜索数据时，我们会指定 bool 表达式来对数据进行筛选，同时需要指定每个查询 sort by 字段以及 size，但分布式环境下，我们没有办法确定这 size 个元素要在每个 shard 里取几个元素。所以最基本的思路：
- 每个 shard 里都取出 size 个元素
- 拉到中心节点来进行多路归并，输出前 size 个元素
- 每个 shard 返回的 size 条数据可以预先排序好。
参考上面的三条，先做局部排序，再做全局归并，思路也不难，先把大 slice 区分成 N 个 slice，然后对每个 slice 进行排序，这个过程用 N 个 g 并发进行。然后建立一个小顶堆，比较依据为每个 slice 的头部元素。
建立好堆之后，每次从堆顶取元素，将堆顶 slice 的 idx++，如果已经取完了该 slice 的元素，则对堆进行 pop。如果没取完，则需要对小顶堆进行再平衡。
基本思路就是这样，剩下的就是各种调试了。。。
我的代码在：这里
有时间应该对 style 进行一些优化。
这里比较麻烦的是，对任务进行切分，并且对局部数组并发排序时，这个拷贝操作怎么都避免不了，否则因为 cpu 的多级 cache 机制导致整体的数组数组被排乱掉。其实就是有 race。
相比标准的 sort.Slice 原地排序，有大量的内存拷贝操作。。没想到有什么好办的优化方法。
~/t/t/mergesort ❯❯❯ make bench master ✱ ◼
go test -bench Benchmark -run xx -count 5 -benchmem
goos: darwin
goarch: amd64
pkg: pingcap/talentplan/tidb/mergesort
BenchmarkMergeSort-8 1 1039028165 ns/op 134228352 B/op 57 allocs/op
BenchmarkMergeSort-8 1 1065523444 ns/op 134222144 B/op 43 allocs/op
BenchmarkMergeSort-8 1 1064337935 ns/op 134222688 B/op 44 allocs/op
BenchmarkMergeSort-8 1 1051075587 ns/op 134221984 B/op 41 allocs/op
BenchmarkMergeSort-8 1 1047990178 ns/op 134221888 B/op 40 allocs/op
BenchmarkNormalSort-8 1 3277904168 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-8 1 3256987462 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-8 1 3259074652 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-8 1 3327195388 ns/op 64 B/op 2 allocs/op
BenchmarkNormalSort-8 1 3356915213 ns/op 64 B/op 2 allocs/op
PASS
ok pingcap/talentplan/tidb/mergesort 25.773s
