# 排序算法
# 内存排序
内存排序是指整个排序算法都在内存中进行，一般来说排序前会将全量数据加载到内存中。
内排序的种类比较多，不同的排序方式的复杂度也不一样。
# 外排序
外部排序是指当需要排序的数据量大于内存最大可用量时，数据需要借助外部存储器进行排序过程。 外排序常见的是外部归并排序，我们这里只探讨这种排序方式。
外部归并排序可以解析成两部分：
- 内存排序。按照不超过内存大小，将待排序内容分段，每段将数据加载到内存中进行排序。排好序的数据段又称为归并段。 排序完毕的归并段被写入外存中。
- 合并，将外存中的归并段进行归并。同样归并时只加载每个归并段的头（因为1中已经排好序），进行归并后再写回外存中。
我们在上图中可以看到，对于长度 = 10的数据，在内存 = 4的机器中是没法直接使用内存排序的。因此使用外部排序第一步就是用内存排序，分为最大为4的若干归并段。 之后第二步合并时，同样使用最大不超过4的内存，每次合并k个，称为k路平衡归并。这里k=2，又被称为2路平衡归并。
我们会发现，对于m个归并段，使用k路归并来说k值越大，归并的次数越少。设归并的次数为s，那么s = 。并且由于每次归并都会在经历一次读外存的过程，因此我们希望k尽可能大。
但与此同时，k值的增大意味着同一时间需要加载到内存中的归并排序数据变多。因此我们会发现当m变多时，归并排序的cpu耗时也会增加。
因此我们优化外部归并排序的点在于：
- 尽可能增加k路排序的k。
- 尽可能减少初始归并段数量m。
下面介绍几种不同的优化思路。