mutiMergeSort

在这个实验中，你需要借助前面所学的多线程的知识，完成一个归并排序和去重操作的程序。待排序的数据是 int 范围的整数，你需要将这些数从小到大排序，并去掉其中多余的重复元素，确保每个元素只出现一次。

任务说明

你只需要修改msort.c文件，对其他任何文件造成的修改 都会被忽略。在msort.c文件中，你可以任意定义数据结构并使用它们，没有任何代码框架上的约束。

详细过程

1）首先，读入一个整数元素的数组，比如：

2 5 3 1 6 4 9 7 8 2 3 8 6 4 7 9

2）根据给定的 分块数 count（从命令行参数中读入，后面会详细说明），将整个数组分成 count份。如果一共有 n 个元素，且 n 除 count 的余数是 x，那么前 x 块有 n/count+1 个元素，后面的块有 n/count 个元素，一共刚好 n个元素。如果上面这组数据的分块数为 3，那么分块后的结果如下：

块 1: 2 5 3 1 6 4

块 2: 9 7 8 2 3

块 3: 8 6 4 7 9

3）对每块数据，使用qsort将每部分数据从小到大排序，qsort的使用方法如下： 将 cmp 函数定义在 qsort 调用之前即可

int cmp(const void\* a, const void\* b) {
    return \*(int\*)a \- \*(int\*)b;
}
// dat 是 int 类型的数组，cnt 是要排序的元素个数
qsort(dat, cnt, sizeof(int), cmp);

注意，在这里需要用 多线程 来并行地对每一块数据进行排序。排序完成后，需要输出一行信息到stderr中：Sorted 5 elements，其中 5 表示这一块中的元素个数。

初始的所有块都完成排序后，需要输出一行Finish firstly sorting到stderr中。

4）完成对每一块数据的排序后，需要一轮一轮将这些块按序合并。

对于每一轮合并，若当前的块数为 remain，则将当前的第 1 块和第 2 块，第 3 块和第 44 块……依次合并，合并后，剩余块数是 ⌈remain/2⌉。也就是说，如果 remain 是奇数，则不会将最后一块跟前面任意一块进行合并。

在合并过程中，要保持合并后的结果依然是遵循从小到大的顺序，并在合并的同时完成对重复数据的删除。对每两个块的合并及删除过程完成后，需要输出以下信息到stderr：Merged 5 and 7 elements into 10 elements，其中 555 是之前更靠前的块内元素个数，7是之前更靠后的块内元素个数，10 表示去掉重复元素以后，合并剩余的元素个数。

注意，这里需要用到 多线程 来并行地对每一对待合并的块完成合并操作。待一轮中所有线程计算完毕后，需要输出一行Finish round 3 merging到stderr，其中 3 表示这次是第几轮合并（轮次从 1 开始编号）。

5）将数组排序并去重后的所有元素逐行输出到标准输出stdout中，比如对于我们前面举例的数据，输出结果就是：

1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9

本地测试

data目录下有两组，共 6 个文件。其中stdin[1/2]文件表示输入文件，即待排序的数据；stdout[1/2]表示标准输出的正确答案；stderr[1/2]表示输出到stderr的正确答案。

你可以在本地执行make对你的程序进行编译及评测。请注意，你无须担心线程执行的顺序问题，也就是说，对于在Finish之前或两个Finish之间的信息，你只需要确保结果正确，而无需确保顺序和标准答案完全一致。

来源

计蒜客