高效地将许多短排序列表合并为一个长排序列表

Question

我一直在将10000个已排序的列表合并成一个长排序列表。每个列表包含约5000个doubles。

double[] result;// this is the single long sorted list
void merge(double[] x){
    double[] newList=new double[x.length+result.length];
    int i=0,j=0;
    while(i<x.length && j<result.length){
        insert the smaller one
        increment i or j;
    }
    if(i<x.length){
        add the rest
    }
    if(j<result.length){
        add the rest
    }
    result=newList;
}

每次使用这种方法都会分配一个新数组，随着result[]的增长，这并不高效。有什么建议吗？

- Wei Shi

Answer 1

你可以像ArrayList一样处理它，每次需要重新分配时将数组长度加倍，只有在空间不足时才重新分配。虽然最后可能会有相当数量的剩余空间，但由于减少了分配操作，你可以节省处理时间。然后，只需对Result和X进行原地合并即可。

- Chris Flynn

Answer 2

您的内存足以容纳整个结果（大约400Mb），因此您可以容纳所有源，800Mb很大，但不算太大？然后，您可以在一开始快速分配整个答案缓冲区。

如果您愿意使用更多内存，可以采用“加倍”方法。

将1和2合并形成A1，3和4合并形成A2等，直到A2500（现在可以丢弃第一级数组）

然后将A1和A2合并形成B1； A3和A4合并形成B2，直到B1250（现在可以丢弃A数组）

依此类推，得到C1-C625，D1-D313，E1-E157 ... M1，这是最终答案

这样，任何给定数字都会移动15次，而目前每个数字都会移动5000次。

- djna

---

我认为：“将1和2合并形成A1，将2和3合并形成A2”应该改为：“将1和2合并形成A1，将3和4合并形成A2”？ - Matt Wonlaw

不需要太高级。OP有已知数量的数组，每个数组中元素的数量也是已知的。如果空间不是问题，将所有元素添加到一棵树中，然后将该树转换回列表。这样做会浪费空间，但时间效率高。如果时间不是问题，请在每个列表的“头”处找到最小的元素并添加它。时间复杂度会很高，但空间效率会尽可能地高。这是一个“就这么做吧”的问题。 - Julie in Austin

Answer 3

将您的问题视为合并排序的合并部分。创建两个足够大的数组来容纳所有小列表的内容。然后在合并步骤中交替使用它们作为源和目标存储。

- jackrabbit