mapreduce中shuffle中两种排序算法

shuffle阶段分为

1. map shuffle也称为shuffle writer, 每个map 处理分配的split, 然后写入到环形缓冲区中，当缓冲区中的数据达到 一定比率，就会开启线程将缓冲区中的数据写入文件，称为spill, spill 同时会对数据进行分区、排序、合并操作，然后写入到文件，这是一个边写缓冲区，边spill的过程，中间可能会产生多个文件，只到map 读取数据完毕会将spill 的所有小文件进行分区、排序、合并成为最终一个数据文件一个索引文件。

2. reduce shuffle 也称为shuffle reader, 待map阶段执行完成，每个reducer开启若干线程 从所有的map阶段输出的索引文件与数据文件获取对应的分区数据，若内存足够则存放在内存中，否则输出到磁盘，在这个过程中还会同时对内存、 磁盘数据进行合并（merge）、排序，最终形成一个有序的大文件，提供给reduce执行。

在shuffle writer 与shuffle reader阶段都发生按照数据的key进行排序，spill 过程对内存缓冲区的数据进行快速排序，map最终合并小文件并归排序，shuffle reader 拉取map端的数据并归排序。用到两种排序算法：快速排序与并归排序。

快速排序：将一串无序的数据使用分而治之的思想排成有序的数据，最终使数据有序，初始选择数组array的下标start,end（start<=end）,选取该下标范围内的一个数据，通常是tmp=array[start], 每一次遍历找到tmp在数组中的位置m使得，数组左边的数据小于等于tmp,右边的数据大于tmp, 然后将数组分为[start,m-1],[m+1,end]两部分，然后分别遍历，如此递归下去最终使array有序。遍历方法：选取的tmp=array[start]作为一个新的空缺位，先从右至左遍历，找到一个小于等于tmp的数据，然后将该数据赋填充到start位置， 那么此时新的end位置空缺，然后从左志右遍历，找到一个大于tmp的数据，然后将该数据填充到新的end位置，依次反复交替直到start=end, 此时的start位置便是数据tmp的位置。示例图如下：

代码实现：

并归排序：将多个有序数组，合并成为一个有序的数组。先考虑将两个有序数组排序思路：分别遍历两组有序数据，a1,a2 ,起始位置都是0， 比较a1[0]与a2[0]的大小关系，将较大的数据存放在空数组c[0]中，若a1[0]>a2[0],则c[0]=a2[0], 然后比较a2[1]与a1[0]的大小关系，依次交替比较，只到其中一个数组取完，将未取完的数组的剩下部分依次存放在c后面。示例图如下：

实现代码：