O(nlogn) worst case : binary search and o(1) space


#1
public class Solution {
    int binarySearch(ArrayList<Integer> arr, int low, int target) {
        int high = arr.size()-1, mid;
        while(low <= high) {
            mid = (low+high)/2;
            if(arr.get(mid) == target) return mid;
            if(arr.get(mid) > target) high = mid-1;
            else low = mid+1;
        }
        return low;
    }
    public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
        int n = a.size(), m = b.size(), lastIndex = 0;
        for(int i = 0 ;i < m;i++) {
        if(b.get(i) > a.get(lastIndex)) { 
            lastIndex = binarySearch(a, lastIndex, b.get(i));
        }
        a.add(lastIndex, b.get(i));
        lastIndex++;
        }
        return;
    }
}

Correct me if time assumption is wrong. I think this is efficient than editorial solution