88. Merge Sorted Array Leetcode Java

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Solution:

It is a very basic problem, which should be solved in a very concise way. First of all, since the A has enough space for this merge, which means from index m to m+n-1 is available for operation. We compare the two arrays from biggest to smallest value, which can make the sort just in one time iteration. We maintain three pointers, i for current lelement in A, j for current element in B, the other one ind for current insertion place for sorted array.

Compare the A[i] with B[j] put the bigger one into A[ind]

Time complexity: O(m+n)

 public void merge(int A[], int m, int B[], int n) {  
     if(A==null || B==null) return;  
     if(n==0) return;  
     int i=m-1;   
     int j=n-1;  
     for(int ind=m+n-1;ind>=0;ind--){  
       if(j<0) return;  
       if(i<0) A[ind]=B[j--];  
       else{  
         if(A[i]>=B[j]) A[ind]=A[i--];  
         else A[ind]=B[j--];  
       }  
     }  
   }