careercup-排序和查找 11.4

11.4 設想你有一個20GB的檔案，每一行一個字元串。請說明将如何對這個檔案進行排序。

解法：

當面試官給出20GB大小的限制時，實際上在暗示些什麼。就此題而言，這表明他們不希望你将資料全部載入記憶體。該怎麼辦呢？做法是隻将部分資料載入記憶體。

我們将整個檔案劃分為許多塊，每個塊xMB，其中x是可用的記憶體大小。每個塊各自進行排序，然後存回檔案系統。各個塊一旦完成排序，我們便将這些塊逐一合并在一起，最終就能得到全都排好序的檔案。

這個算法被稱為外部排序。