无法理解在外部合并排序中将多大块数据加载到 RAM 中
Not able to understand the how bigger chunks data is loaded into RAM in external merge sorting
今天朋友问我：
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 merge sort，根据它：
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 chunks 数据的 RAM，并且我们有 6 chunks 数据要排序。请看下图：
因为我们的记忆可以容纳 2 chunks of data 所以第一个 step 1 听起来是合理的，因为我们只对数字对 (5,6), (3,4) (1,2) 进行排序。在 step 2 中，我们合并数据，现在我们的块大小为 4。我的问题是现在如何将 4 chunk of data 加载到内存中？由于您的内存不能接受超过 2 个数据块，那么您如何加载和排序它们？在此处合并数据块时，您是如何排序的？我访问了几个链接，但无法理解这个概念。
您一定在合并数据的同时进行了某种排序，对吗？这个问题听起来可能很愚蠢，但我无法理解，如果有人能帮助我，我将不胜感激。
现在我的疑惑解开了：
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.
如果您看到 merge sort link 的可视化，一旦列表排序，那么它就是合并，我们现在不需要任何临时 space。
有 (3, 4, 5, 6) 和 (1, 2)。现在比较两个块数据。
first指针表示第一个chunk数据，second指针表示第二个chunk数据。然后，第一个指针指示 3，第二个指针指示 1。
比较 3 和 1，1 很小，所以 1 被保存并超出内存。
第一个指针相同，第二个指针指示 2，依此类推。
不只是加载整个大小的块数据。它被排序所以我们只知道每个块数据的第一个数字（最小）并只比较两个数字。
今天朋友问我：
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 merge sort，根据它：
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 chunks 数据的 RAM，并且我们有 6 chunks 数据要排序。请看下图：
因为我们的记忆可以容纳 2 chunks of data 所以第一个 step 1 听起来是合理的，因为我们只对数字对 (5,6), (3,4) (1,2) 进行排序。在 step 2 中，我们合并数据，现在我们的块大小为 4。我的问题是现在如何将 4 chunk of data 加载到内存中？由于您的内存不能接受超过 2 个数据块，那么您如何加载和排序它们？在此处合并数据块时，您是如何排序的？我访问了几个链接，但无法理解这个概念。
您一定在合并数据的同时进行了某种排序，对吗？这个问题听起来可能很愚蠢，但我无法理解，如果有人能帮助我，我将不胜感激。
现在我的疑惑解开了：
If you see the pseudo for
merge sortif 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.
如果您看到 merge sort link 的可视化，一旦列表排序，那么它就是合并，我们现在不需要任何临时 space。
有 (3, 4, 5, 6) 和 (1, 2)。现在比较两个块数据。 first指针表示第一个chunk数据，second指针表示第二个chunk数据。然后，第一个指针指示 3，第二个指针指示 1。 比较 3 和 1，1 很小，所以 1 被保存并超出内存。 第一个指针相同，第二个指针指示 2，依此类推。
不只是加载整个大小的块数据。它被排序所以我们只知道每个块数据的第一个数字（最小）并只比较两个数字。