为什么我们应该使用 n 路合并？与2路合并相比，它有什么优势？

我尝试阅读一些有关 n-way merge 的文章，但不理解这个概念。我很困惑为什么你会使用 n 路合并而不是 2 路合并？就像为什么要将数组分成 3 部分，对它们进行排序，然后对 2 部分进行 2 路合并，然后将第 3 部分与此合并的 2 部分进行 2 路合并:)

Thanks

当您进行外部排序时，您通常最终会合并多个流。例如，假设您需要对 1 TB 的数据进行排序，并且只有（比如说）64 GB 的 RAM。

通常，您会读取 64 GB 的数据，对其进行排序，然后将其写出。对整个 TB 数据重复此操作，为您可以一次性保存在内存中的每个“块”生成一个中间文件。有多种方法可以改进这一点，但您通常可以期望的最好结果是生成每个大约 128 GB 的排序中间文件。

这就留下了许多需要合并在一起的中间文件——而且这个数字几乎肯定会大于 2。

如果您定期执行此操作，则可能有一些相当高端的硬件可以使用。如果您将每个中间文件放在单独的磁盘驱动器上（并且至少还有一个用于输出），您几乎肯定可以通过一次将所有数据合并在一起（而不是一次只合并两个数据）来提高速度。该过程通常受 I/O 限制，因此一次从（比如说）8 个磁盘读取的速度通常是一次仅从 2 个磁盘读取的速度的 4 倍左右（尽管这取决于您的输出磁盘具有那么多带宽） ，这可能不是真的）。通过避免创建更多中间文件（这将需要进一步合并），您的整体速度可能会提高更大的系数。