Java Solution Without using extra space in O(n)


#1

public class Solution {
public void merge(ArrayList a, ArrayList b) {

    int i =0;
    int j =0 ;
    while(i<a.size()&&j<b.size()){
        if(a.get(i)>=b.get(j)){
            a.add(i,b.get(j));
            j++;
        }
        else if(a.get(i)<b.get(j)){
            i++;
        }
    }
    if(j<b.size()){
        while(j<b.size()){
            a.add(b.get(j));
            j++;
        }
    }
}

}


#2

a.add(i, b.get(j)) runs in O(n) worst case time, so the worst case time for this solution is O(n^2).

public void add(int index, E element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

(source: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html#add-int-E-)