java - 有效地将许多短排序列表合并成一个长排序列表

Question

我反复将 10000 个排序列表合并为一个长排序列表。每个列表包含大约 5000 个 double。

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[] 的增长，这是不高效的。有什么建议吗？

Answer 1

您可以像 ArrayList 一样处理它，并在每次需要重新分配时将数组的长度加倍，然后仅在空间不足时才重新分配。尽管最后可能有相当数量的剩余空间，但由于分配较少，您可以节省处理时间。然后就地与 Result 和 X 进行合并。