1. 笔记

归并排序使用的就是分治思想。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了。

分治算法一般都是用递归来实现的。分治是一种解决问题的处理思想，递归是一种编程技巧。

递归代码的编写技巧：分析得出递推公式，然后找到终止条件，最后将递推公式翻译成递归代码。

归并排序是一个稳定的排序算法。

第二，归并排序的时间复杂度是多少？
归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是O(nlogn)。

第三，归并排序的空间复杂度是多少？
空间复杂度是O(n)。

快速排序的原理
快速排序并不是一个稳定的排序算法。

内容小结
归并排序和快速排序是两种稍微复杂的排序算法，它们用的都是分治的思想，代码都通过递归来实现，过程非常相似。理解归并排序的重点是理解递推公式和merge()合并函数。同理，理解快排的重点也是理解递推公式，还有partition()分区函数。

归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法，这也使它存在致命的缺点，即归并排序不是原地排序算法，空间复杂度比较高，是O(n)。正因为此，它也没有快排应用广泛。

快速排序算法虽然最坏情况下的时间复杂度是O(n2)，但是平均情况下时间复杂度都是O(nlogn)。不仅如此，快速排序算法时间复杂度退化到O(n2)的概率非常小，我们可以通过合理地选择pivot来避免这种情况。

2. 疑惑

展示分区操作的那个图不是很理解

3. 思考题

现在你有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB，你有什么好的解决思路，能“快速”地将这10个日志文件合并吗？

我感觉评论中的高手说的很对。我就简单的记录一下。

先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存，这是我想出的认为最好的操作了。

4. 实际场景

消息系统的全局有序性的实现。