以前电话面试曾经被问到一个题目，如果只有4G内存，但是需要对200G数据进行排序，应该怎么操作。当时的反应就是进行外部排序，但是具体怎么外部排序我却说的不明不白。觉得知识有些时候还是需要拿出来晒一晒，不然发霉了就不好了。
1.问题提出
有4个G内存，需要对磁盘上200G数据进行排序，如何进行？
2.采用归并排序思想
将所有数据一起加载进内存进行排序是显然是不可能的，所有需要分段进行排序。
（1）将200G的磁盘数据分为50个4G数据，比如编号0~49，然后依次加载进内存进行内部排序，结果为50个数据段，数据段内部是有序的；
（2）取0和1号数据段准备操作。先从0号数据段中取前1G数据，再从1号数据段中取前1G数据，进行归并（内部排序），然后将排序后的数据写回到磁盘上，在写回的过程中，当某个数据段的数据写完时（比如排序完之后回写数据过程中，发现剩下的数据都是1号数据段的，此时应该再从0号数据段中加载1G的数据与剩下的未写回的数据一同排序）。示意图如下。
0号数据段：6 3 1 4 8 12 56 34
1号数据段：2 36 5 7 9 10 11 24
内存大小为8个数据
1、先对所有的数据段进行内部排序：
0号数据段：1 3 4 6 8 12 34 56
1号数据段：2 5 7 9 10 11 24 36
2、从0号与1号数据段分别取4个数据，加载到内存进行排序，为了区分其中[]中的为1号数据段的数据：
1 [2] 3 4 [5] 6 [7] [9]
3、依次将排序好的数据写回到磁盘，当某一个数据段中的写完了停止。如下，此时剩下的都是1号数据段的数据：
[7] [9]
4、从0号数据段再加载4个数据，然后进行内部排序，内存中的数据如下：
[7] 8 [9] 12 34 56
5、重复步骤3，结果如下：
12 34 56
6、从1号数据段再加载4个数据，然后进行内部排序，内存中的数据如下：
[10] [11] 12 [24] 34 [36] 56
7、因为0号与1号数据段已经没有剩余数据了，将内存中的数据全部写回磁盘即可。磁盘中数据如下，排序完毕。
1 [2] 3 4 [5] 6 [7] 8 [9] [10] [11] 12 [24] 34 [36] 56（3）然后依次将2号与3号、4号与5号...48号与49号数据按照步骤（2）进行排序，生成25段8G的有序数据；
（4）重复（2）（3）步骤，直至最后剩下一段200G的有序数据。
3.感想
因为当时上数据结构课时，老师跳过了此节，所以自己觉得可能不重要，但终究在面试中挖了个大坑。个人一直对外部排序困惑的地方在于为什么两个有序的数据段局部A1、B1合并成一个有序的数据段局部C1，这个C1就是C的一部分。后来才发现，关键点在当输出数据时，当A1的元素输出完毕时，就需要再加入新元素A2与B1混在一起进行排序，而不能全部输出，因为可能A2中存在排在B1前面的元素。