如果我在外部内存中存储了一个非常大的列表，需要对其进行排序。如果这个列表对于内部内存来说太大，那么在设计外部排序算法时应该考虑哪些主要因素？
在构建自己的外部排序之前，您可能会查看操作系统提供的工具。Windows有SORT.EXE，它在一些文本文件上运行得很好，尽管它有。。。特质。GNU类型也运行得很好。你可以在你的数据子集上尝试这两种方法，看看它们是否能满足你的需求。
否则。
外部排序是一种非常著名的算法。总体思路：
- 将尽可能多的数据加载到内存中
- 对那个块进行排序
- 将该块写入外部存储器
- 重复步骤1-3，直到所有块都已排序并存储
- 合并已排序的块
假设您有n项，这些项被分离为k块，每个块由m个元素组成（因此为n = k*m），则第一部分（步骤1-4）所花费的时间与k*（m log m）成比例。
完成步骤1-4后，您将获得k排序的m项目块（或者可能是k-1的m项目块，以及一个项目较少的块）。或者，如果对字符串进行排序，则会有大小大致相同的k块，但每个块中的字符串数会有所不同。
您现在需要合并这些已排序的块。典型的方法是使用k路合并。
您创建一个最小堆，其中包含每个块中的第一个项。然后从堆中选择根项目，它是所有块中最小的项目。您将其作为第一项输出。然后，从最小的块中读取下一个项目，并将其放在堆上。即：
create heap
for each block
read item and add to heap
end for
while heap is not empty
remove smallest item from heap
write to output
read next item from block that contained smallest item
add to heap
end while
算法的这一部分是O（n-logk），其中n是项目的总数，k是块的数量。
正如其他人所指出的，高效外部排序的一个关键是减少I/O。外部存储速度较慢。我上面描述的算法尽可能少地执行I/O操作。每个项目从外部存储器读取两次，每个项目写入外部存储器两次。其他乍一看更简单或更快的算法在处理真实数据时会慢得多，因为它们花了太多时间进行I/O。
如果您对实现感兴趣，我曾写过一系列关于对一个非常大的文本文件进行排序的文章。代码是C#，但描述应该可以让你毫不费力地翻译成任何语言。