Cracking the coding interview--Q9.4

题目

原文：

If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

译文：

如果你有个2GB的文件，其中每一行是一个字符串，你会使用哪种算法来排序，为什么？

当面试官说到2GB文件的时候，他其实就是在暗示你，他并不希望一次性把所有的数据都载入内存。这样子的话，我们要怎么做呢？我们每次就将部分数据载入内存就好了。

算法：

首先我们要了解，可以用的内存有多大？假设我们有X MB的内存可用。

上面的算法就是外排序，步骤3又称为N路归并。

使用外排序是由于数据太大了，无法一次全部加载到内存中，所以需要借助磁盘进行存储，每次只从磁盘中加载一部分数据进入内存，进行排序。