Fastest way to Merge two arraylists

user_11397075 0
Viewed 371

I'm trying to merge two lists in sorted order, and I was wondering what the fastest way to merge them would be. Currently, my algorithm is basically (ignoring syntax):

merge(a, b){
    newlist = new Arraylist()
    while(!a.isEmpty() && !b.isEmpty()){
        if(a.get(0) > b.get(0))
            newlist.add(a.remove(0))
        else 
            newlist.add(b.remove(0))
    }
    newlist.addAll(a)
    newlist.addAll(b)
    return newlist
}

Is there a faster way to do this kind of merge? I'm trying to reduce my runtime as much as possible as this function is called thousands of times with very large ArrayLists.

merge java
3 Answers

Removing from the front of an ArrayList has O(N) time complexity since all other elements need to be shifted. Instead, you could store the current index of the two Lists and compare the elements at the the indexes each time to merge in O(N) time complexity overall (taking advantage of the fact that both Lists are already sorted). Note that this is generally the method used in a merge sort. Also, it is better to pass the initial capacity to the ArrayList constructor if you know the size at the end.

public static List<Integer> merge(List<Integer> a, List<Integer> b){
    List<Integer> result = new ArrayList<>(a.size() + b.size());
    int left = 0, right = 0;
    while(left < a.size() || right < b.size()){
        if(right == b.size() || left < a.size() && a.get(left) <= b.get(right)){
            result.add(a.get(left++));
        } else {
            result.add(b.get(right++));
        }
    }
    return result;
}
user_95131840

should using parallelism for the merging be similar fast?

public static List<Integer> merge(List<Integer> a, List<Integer> b) {
    return Stream.concat(a.parallelStream(), b.parallelStream())
        .sorted().collect(toList());
}

(I really be interested in whether the speed advantage justifies the higher programming effort of the chosen solution.)

user_111998790

For any performance question: you'll have to measure with your own data.

In this case: initialize your Array List with the expected size, so that it doesn't need to be resized. But that is only a starting point

user_134470
Related