algorithm - 无法理解在外部合并排序中将多大块数据加载到 RAM 中

Question

今天我 friend 问我:

Write a program to sort millions of element in your list but memory size is very small. It cannot hold more than 100 elements.

我正在从维基百科文章 link 中阅读有关外部归并排序 的内容, 根据它:

External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.

假设我们有一个只能容纳 2 block 数据的 RAM，而我们有 6 block 数据要排序。请看下图:

由于我们的内存可以容纳 2 个数据 block ，因此第一个 第 1 步 听起来很合理，因为我们只对数字对 (5,6)、(3, 4)(1,2)。在第 2 步 中，我们合并了数据，现在我们的 block 大小为 4。我的问题是现在如何将这 4 block 数据 加载到内存中？由于您的内存不能接受超过 2 个数据 block ，那么您如何加载和排序它们？在此处合并数据 block 时，您是如何排序的？我访问了几个链接，但无法理解这个概念。

您一定在合并数据的同时进行了某种排序，对吧？这个问题听起来可能很愚蠢，但我无法理解，如果有人能帮助我，我将不胜感激。

Answer 1

现在我的困惑被清除了:

If you see the pseudo for merge sort if the two list are stored then merging them will take only O(1) time only. You can see that Merge only needs O(1) memory to merge two sorted lists, even if the sorted lists are stored in external storage -- it never needs to load the input lists into memory in their entirety.

如果您看到合并排序 的可视化 link一旦列表被排序，那么它就是关于合并的，我们现在不需要任何临时空间。