Merge many short sorted lists into a long sorted list efficiently

I'm repeatedly merging 10000 sorted lists i开发者_JAVA百科nto a single long sorted list. Each list contains about 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;
}

This method allocates a new array every time. As result[] grows, this is not efficient. Any advise?

You could handle it the same way ArrayList does and double the length of your array every time you need to reallocate and then only reallocate when you run out of space. Although you might have a fair amount of leftover space at the end, you would save processing time due to less allocations. Then just do an in-place merge with Result and X.

You clearly have enough memory to hold the entire result (400Mb is it?) so presumably you could hold all the source too 800Mb is big, but not too big? Then you can quick allocate the entire answer buffer right at the start.

If you are prepared to use even more memory you could take a "doubling" approach.

Merge 1 & 2 to form A1, 3 & 4 to form A2 etc. up to A2500 (you can now discard the first level arrays)

Then merge A1 and A2 to form B1; A3 & A4 to form B2 up to B1250 (you now discard the A arrays)

And so on yielding C1-C625, D1-D313, E1-E157 ... M1, which is the final answer

This way any given number gets moved 15 times whereas at present you move every number 5000 times.

See your problem as the merging part of a merge-sort. Create 2 arrays that are big enough to hold the content of all the small lists combined. Then use them alternatingly for source and target storage in the merge steps.