如何外部归并排序算法的工作？ [英] How external merge sort algorithm works?
问题描述
我想了解外部合并排序算法的工作（我看到了一些答案，同样的问题，但没有找到我所需要的）。我读的书分析算法杰弗里·麦康奈尔，我试图执行那里介绍的算法。
I'm trying to understand how external merge sort algorithm works (I saw some answers for same question, but didn't find what I need). I'm reading the book "Analysis Of Algorithms" by Jeffrey McConnell and I'm trying to implement the algorithm described there.
例如，我有输入数据： 3,5,1,2,4,6,9,8,7 ，我可以只加载4个号码为内存。
For example, I have input data: 3,5,1,2,4,6,9,8,7, and I can load only 4 numbers into memory.
我的第一个步骤是读取4号块输入文件，对它们进行排序在内存中，并写入一个文件A和旁边的文件B。
My first step is read the input file in 4-number chunks, sort them in memory and write one to file A and next to file B.
我：
A:[1,2,3,5][7]
B:[4,6,8,9]
现在我的问题我怎么能合并这些文件是较大的块，如果他们将不适合的内存？杰弗里·麦康奈尔写道，我需要阅读半块，并将其合并到下一个文件，C和D。
Now my question how can I merge chunks from these files to the bigger ones if they will not fit to the memory? Jeffrey McConnell wrote that I need to read half chunks and merge them to next files C and D.
但我错了顺序：
C:[1,2,4,6,3,8,5,9]
D:[7]
任何人都可以提供一个例子一步一步的指导，好吗？
Can anyone provide an example with step by step instruction, please?
PS：我知道如何合并数按编号从文件中读取数据，但我怎么做它在内存缓冲区，以减少I / O操作
PS: I understand how to merge number by number by reading from file, but how do I do it with in-memory buffers to reduce I/O operations?
推荐答案
我后，你一定已经有了答案这么长的时间猜测。但我还是提供了一些例子链接，以帮助别人谁打了这个问题。
I guess after such a long time you must have got an answer. But I am still providing some example links to help someone else who hits this question.
注：之前寻找到这个环节，你有关于堆数据结构的想法 看看 <一个href="http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L17-ExternalSortEX1.htm">link1和<一href="http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L17-ExternalSortEX2.htm">link2你会得到一个外部排序算法的实现
NOTE: Before looking into this link you should have an idea about Heap data structure Take a look at link1 and link2 and you will get a complete idea of the implementation of a external sorting algorithm
这篇关于如何外部归并排序算法的工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
