An simple implement of K partition merge sorting algorithm.
BUILT WITH Bazel
算法使用了败者树来进行K分区归并排序，使得总的时间复杂度在O(nlogn)的前提下，占用的额外内存和比较次数尽可能少。
在Partition类的设计中，对外有get_next与add_number两个public的方法。这是为了使得数据块不管是存在内存里，还是硬盘里或者分布式存储当中，外部程序都能够用这两个方法来获取下一个需要的数以及往分区里加入一个数（不必保证有序）。相当于抽象出来了一个IO层。目前代码的实现中只考虑了在内存中的情况。
该算法占用内存和比较次数都很优秀，主要的瓶颈在于获取下一个数以及写入一个数的速度。该速度取决于数据存放的位置，根据位置不同受访存速度，磁盘IO速度，网络带宽等的影响。当然实际使用中可以一次读入一个DataBlock在内存里缓存，攒够一个DataBlock再写入到硬盘或者分布式存储中，以此提高效率。
bool Partition::get_next(int &x);
void Partition::add_number(int x);
在test.cpp文件中对该算法进行了简单的测试。
Partition 0: 11 228 392 543 716 | 903 1141 1317 1482 1641 | 2267 2409 2679 2874 3137 | 3470 3663 4173 4456 4952 |
Partition 1: 92 257 452 604 745 | 939 1167 1348 1496 1787 | 2293 2437 2716 2919 3143 | 3478 3730 4181 4500 4981 |
Partition 2: 106 259 452 645 792 | 1014 1211 1376 1526 1790 | 2348 2497 2749 2974 3168 | 3510 3870 4203 4608 5039 |
Partition 3: 155 302 507 659 798 | 1018 1239 1429 1548 1821 | 2362 2535 2750 3043 3375 | 3642 3878 4263 4764 5150 |
Partition 4: 185 373 527 673 810 | 1040 1262 1458 1621 2034 | 2388 2601 2793 3113 3457 | 3648 4167 4396 4942 5202 |
After merge:
11 92 106 155 185 228 257 259 302 373 392 452 452 507 527 543 604 645 659 673 716 745 792 798 810 903 939 1014 1018 1040 1141 1167 1211 1239 1262 1317 1348 1376 1429 1458 1482 1496 1526 1548 1621 1641 1787 1790 1821 2034 2267 2293 2348 2362 2388 2409 2437 2497 2535 2601 2679 2716 2749 2750 2793 2874 2919 2974 3043 3113 3137 3143 3168 3375 3457 3470 3478 3510 3642 3648 3663 3730 3870 3878 4167 4173 4181 4203 4263 4396 4456 4500 4608 4764 4942 4952 4981 5039 5150 5202 |