Merge two sorted array into a

Merge two sorted array into a

  May 26, 2018    

---

Simple approach was merge of merge sort but that take extra space

Here we doing in O(1) extra space.

Algo:
Start and check the correct position of jth element of b
add into that position , change size of array a

And import point is also check if previous element added was of b and now we are pointing to next greater element of that and it may arise that previous element is greater than this so add at previous index and don't increment i

Code:

public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
    int i=0,j=0;
    int k=0;
    int n=a.size(),m=b.size();
    while(k<n && j<m)
    {
        if(a.get(k)<b.get(j))
               ++k;
           
         else
         {
             if(k-1>=0 && a.get(k-1)>b.get(j))
             a.add(k-1,b.get(j));
             else
              { a.add(k,b.get(j));
                n=a.size();
             ++k;
            }
             ++j;
         }
    }
    while(j<m)
    {
        a.add(b.get(j++));
    }
}