如何优化合并排序？

Question

我有两个1 GB的文件,每个文件只包含按排序顺序排列的数字.现在我知道如何读取文件的内容并使用合并排序算法对它们进行排序并将其输出到另一个文件但我感兴趣的是如何只使用100MB缓冲区大小(我不担心划痕)空间).例如,一种方法是从两个文件中读取50 MB块并对其进行排序,并且在排序时我可以读取新元素并继续该过程,直到我到达两个文件的末尾(任何人都可以告诉我如何实现这个).

Answer 1

听起来你只需要合并文件中的数字,而不是对它们进行排序,因为它们已经在每个文件中排序.合并排序的merge部分是这样的:

function merge(left,right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) ? first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append left to result
            break             
        else if length(right) > 0
            append right to result
            break
    end while
    return result

现在,您可以从两个缓冲区中的两个文件中读取前50 MB的数字,应用合并算法,然后当其中一个缓冲区已用尽(分析了所有数据)时,从所需文件中读取另外50 MB.没有必要对任何东西进行排序.

您只需要一个条件来检查其中一个缓冲区是否为空.如果是,请从与缓冲区关联的文件中读取更多内容.