Java ArrayList's merge function complexity

user_10033941 0
Viewed 222

I had to write a function that merges two given sorted (from smallest to largest) ArrayList's of Integer's. Merge must be done in the first ArraList (in our case list a) and we must leave the sorted order(from smallest to largest).

 void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
    int currentIndexListA = 0;
    int currentIndexListB = 0;

    while(currentIndexListB < b.size()) {
        if(currentIndexListA == a.size() || a.get(currentIndexListA) > b.get(currentIndexListB)) {
            a.add(currentIndexListA, b.get(currentIndexListB));
            currentIndexListB++;
        }
        currentIndexListA++;
    }
}

So, i'm a few confusing about complexity of algorithm. The task was to make the maximum efficiency algorithm with complexity of O(N). And I think that it's O(N) complexity, but the interviewer responded that the code is inefficient. Is it correct ?

big-o algorithm java
1 Answers

You used ArrayList.add function by index which insert your data at specified position and shift other elements. add function in ArrayList class uses System.arraycopy to shift elements and System.arraycopy uses native implementation with O(N) which N is the number of shifted elements. So you algorithm is not efficient.

A better way as @SomeDude said is using new ArrayList such as following:

import java.util.ArrayList;

public class Main
{
    static void merge2(ArrayList<Integer> a, ArrayList<Integer> b) {
        
        ArrayList<Integer> c = new ArrayList<Integer>();
        int ixa=0, ixb=0;
        int limita = a.size();
        int limitb = b.size();
        int aElem = 0;
        int bElem = 0;
        
        while(ixa+ixb < limita+limitb ) {
            
            aElem = Integer.MAX_VALUE;
            bElem = Integer.MAX_VALUE;
            
            if(ixa < limita) 
                aElem = a.get(ixa);
            
            if(ixb < limitb)
                bElem = b.get(ixb);
                
            if( aElem <= bElem) {
                c.add(aElem);
                ixa++;
            }else {
                c.add(bElem);
                ixb++;
            }
        }

        
        for(Integer aa:c) {
            System.out.println(aa);
        }
    
    }

     public static void main(String []args){
        ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(1,3,5));
        ArrayList<Integer> b = new ArrayList<Integer>(Arrays.asList(2,4,6));
        
        merge2(a,b);
        
        ArrayList<Integer> c = new ArrayList<Integer>(Arrays.asList(1,2,3));
        ArrayList<Integer> d = new ArrayList<Integer>(Arrays.asList(5,6,7));

        merge2(c,d);
     }
}
user_25274580
Related