这个问题看起来很简单，但我无法理解它背后的真正工作。我知道人们会说，分解成 512 Megs 块并像使用 Map reduce 的 Merge Sort 一样对它们进行排序。
所以这是我的实际问题：
假设我将文件分成 512 Megs 块，然后发送到不同的主机对它们进行排序。假设这些机器使用了归并排序。现在说，我有 2000 台机器，每台机器都分类了 2000、512 兆的块。现在，当我将它们合并回来时，它是如何工作的？尺寸不会继续增加吗？例如，合并两个 512 兆将产生 1024 兆，这是我的 RAM 的大小，那么这将如何工作？任何机器都不能将超过 512 megs 的块与另一个块合并，因为那时大小 > 1 GB。
在合并结束时，我将如何能够将两个 0.5 TB 块与另一个 0.5 TB 块合并.. 虚拟内存的概念在这里发挥作用吗？
我来这里是为了澄清我的基础知识，我希望我能正确地（正确地）问这个非常重要的问题。另外，谁应该做这个合并（排序后）？我的机器还是那 2000 台机器中的几台？
这个问题可以简化为一个更简单的问题。这个问题旨在迫使您采取一种方法。这里是：
现在，它只是将 k 排序数组合并到一个新数组中的问题。
合并 k 排序数组需要您一次维护一个包含 k 个元素的最小堆（优先级队列）。
即在我们的例子中k = 1000（文件）。（1GB 内存可以存储 1000 个数字）
因此，请不断从优先级队列中弹出元素并保存到磁盘。
您将拥有一个大小为 1TB 的新文件。
参考：http ://www.geeksforgeeks.org/merge-k-sorted-arrays/
更新
PS：可以在1GB RAM的单机上完成，数据结构更好
合并可以在少于O(N) 的空间内完成，优先级队列即O(K) 空间，即问题的核心。
你如何合并的简短版本是这样的：
1）您为要合并的每台机器创建一个带有一个插槽的表。
2）您要求每台机器提供他们尚未给您的最低条目。
3）你从你的表中删除最低值的条目，输出它，并要求该机器用它尚未给你的最低条目重新填充慢速，如果机器没有条目，则将插槽留空。
4) 重复第 3 步，直到表格为空。
这允许您从 N 台机器合并一次仅存储 N 个条目。当然，您可以简单地优化它以保存来自每台机器的 M 个条目。在这种情况下，您需要存储 N*M 个条目，当一个插槽为空时，请该机器提供 M 个条目以重新填充它。
这是一种应该有效的理论方法。假设您有 2000 个 512mb 文件，准备创建一个 1TB 文件。
如果您只是遍历每个文件，找出哪个文件的 FIRST 值最低，然后将其移至目标文件中，然后重复一遍，您将得到所有内容。RAM 使用量应该很小，因为您一次不需要打开超过一行。
显然，您应该能够对此进行优化 - 将每个文件的第一行保留在 RAM 中，它应该会更快一些。
现在说，我有 2000 台机器，每台机器都分类了 2000、512 兆的块。现在，当我将它们合并回来时，它是如何工作的？尺寸不会继续增加吗？例如，合并两个 512 兆将产生 1024 兆，这是我的 RAM 的大小，那么这将如何工作？任何机器都不能将超过 512 megs 的块与另一个块合并，因为那时大小 > 1 GB。
这不是实际的合并排序实现的工作方式。归并排序（和相关的排序算法）的一个很酷的地方是，您不需要将整个数据集放在内存中即可使其工作。合并时，您只需一次将文件的一小部分读入内存，然后很快就会写出。
换句话说，合并排序不需要随机访问。如果没有这个好特性，就不可能使用当时可用的技术对磁带驱动器上的数据进行排序。磁带驱动器当然不是随机存取介质，当时的 RAM 以千字节为单位。
合并排序的好处是您不需要随机访问。顺序访问就可以了。当数据集不适合内存时，这就是使其成为完美解决方案的原因。
单个合并过程需要 2 个（或更多）输入并产生一个输出。您只需将输入组合到输出中，直到只剩下一个文件。