2018-3-22
外排序思路：https://www.cnblogs.com/codeMedita/p/7425291.html
外排序：使用
- 优化
假设我现在把文件中的2G数据载入内存这个过程定义为”L”，把内存中的排序过程定义为”S” ,把排序好的 2G数据再转储到另一个文件这个过程定义为”T”…
使用“用流水线并行实现“优化，
在“S”这个过程，也就是内部排序的这个环节最好不要用“快速排序”，因为快速排序是不稳定的排序，所以在流水线那个图中会出现不均匀的时间块，影响整体性能。
- 加了这个优化之后，某个资源会不会出问题？
内存出的问题，因为，如果并行进行的话，打个比方，比如现在同时处理的过程是，第一个2G数据的“T”阶段（因为第一个2G数据，比较早的进入流水线，所以之前的两个阶段已经处理完毕），第二个2G数据的“S”阶段，第三个2G数据的“L”阶段，那么这三个阶段是都需要把数据放到内存中的，所以一共得需要6G内存，但是目前计算机的实际内存只有2G啊！！！
解决方法很简单，将内存平均分为三份，分别用于处理三个阶段的数据。
这样带来的影响是，现在一次就不能处理2G数据了，只能处理2/3G的数据，流水线会加长。
- 在最后的归并上有什么优化？
最后的归并就是不断在一组有序数列中找最小值，还用刚才那个例子，最后不是得到500个2G有序数列吗，但是扫描每个文件头，找最小值，最差情形要比较500次，平均复杂度是O（n）,n为最后得到的有序数组的个数，此例子为500。
他既然问有没有什么优化？那么必然是存在logn的算法了。一提logn和最小值，那没的说，必须是“堆”啊！！！
就是维护一个大小为n的“最小堆”，每次返回堆顶元素，就为当前所有文件头数值的那个最小值。然后根据刚才弹出的那个最小值是属于哪个文件的，然后再将那个文件此时的头文件所指向的数，插入到最小堆中，文件指针自动后移。插入过程为logn复杂度，但是每次返回最小值的复杂度为O(1)，运行时空间复杂度为O(n)。