采访难题：使用有限的内存对一百万个输入进行排序

我尝试使用外部排序来回答这个问题，但是访问者回答说复杂性是高nn（log（n）），即n square * logn。有没有更好的选择。

简化问题：假设我们有1000个元素要排序，只为100个元素分配空间。什么是比外部排序花费更少时间的最佳算法。

我不知道你（或面试官）的意思，但是

我的建议是10路（在你的情况下）合并：

将文件拆分为MAX_MEM大小的块（100个元素）
- 这是O(1)
对内存中的每个块进行排序，并将其存储为单独的文件
- 这是O((n/max_mem) * (max_mem) log(max_mem))) = O(n log(max_mem))
打开所有块作为元素流
通过选择每个步骤中的最低元素来合并所有流。
- 这是使用minHeap或O(n^2/max_mem) O(n log(n/max_mem)) （在实践中可能更快）
删除块

关于计算，这是O(n (log(max_mem)+log(n/max_mem))) = O(n log(n))

关于磁盘I / O，如果所有合并都在一次传递中完成，则这是2*n读取和2*n写入。更一般地说，它是(1+[depth of the merge tree])*n

所有写入都是顺序的。第一个读取是顺序读取，第二个读取是连续的，从10个文件交错。

如果有更多的数据，你需要重复或递归合并（每个块100个，然后重复选择N个块）。此时，值得用@ amit的答案中的替换/选择替换split + sort步骤，特别是当数据已经几乎排序时（您可以完全避开合并步骤）。

请注意，较高的N可能会增加计算（如果您使用正确的结构，则会非常轻微），但会显着减少磁盘I / O的数量（达到一定数量;如果您一次合并太多的块，则可能会耗尽读缓冲区的内存，导致不必要的读取）。磁盘I / O很昂贵，CPU周期不是。

也许面试官希望你问：这些数字是J. Bentley（ Cracking the Oyster ）提到的独特的七位数电话号码吗？

这样做的标准方法是外部排序。

在外部排序中 – 不仅具有O(nlogn)复杂性很重要 – 尽可能最小化磁盘读/写，并使顺序（而非随机）读取和写入次数最多也是至关重要的 – 因为磁盘访问顺序完成后效率更高。

这样做的标准方式确实是一种k-way合并排序，正如@JanDvorak所建议的那样，但是我想要纠正的建议有一些错误和补充：

首先，对输入执行RS（替换 – 选择）会减少初始“运行”的数量（递增序列的数量），因此通常会减少稍后合并排序所需的迭代总数。
我们需要用于缓冲（读取和写入输入）的内存 – 因此，对于内存大小M和文件大小M * 10，我们不能进行10路合并 – 它将导致大量读取磁盘（读取每个元素，而不是在块）。
k的标准公式 – 合并的“顺序”是M/(2b) （其中M是内存的大小， b是每个“缓冲区”（通常是磁盘块）的大小。
每个合并排序步骤都是通过读取前一次迭代中生成的每个“运行”中的b个条目来完成的 – 在内存中填充M/2 。内存的其余部分用于“预测”（允许连续工作，最少等待IO） – 从运行和输出缓冲区请求更多元素 – 以保证块中的顺序正确。
使用此方法的迭代总数为log_k(N/(2M)) ，其中k是运行次数（先前计算的）， M是内存的大小， N是文件的大小。每次迭代需要1次顺序读取和1次顺序写入整个文件。

也就是说 – file_size / memory_size的比例通常比10更多。如果您只对10的比率感兴趣，可能会发生本地优化，但不适用于file_size/memory_size >> 10的更常见情况。