Merge two given sorted integer array A and B into a new sorted integer array.

Example

A=[1,2,3,4]

B=[2,4,5,6]

return [1,2,2,3,4,4,5,6]

Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

 class Solution {

     /**

      * @param A and B: sorted integer array A and B.

      * @return: A new sorted integer array

      */

     public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {

         // write your code here

         if (A==null || A.size()==0) return B;

         if (B==null || B.size()==0) return A;

         ArrayList<Integer> res = new ArrayList<Integer>();

         int i=0, j=0;

         for (int k=0; k<A.size()+B.size(); k++) {

             if (i<A.size() && j<B.size() && A.get(i) < B.get(j)) {

                 res.add(A.get(i));

                 i++;

             }

             else if (i<A.size() && j<B.size() && A.get(i) >= B.get(j)){

                 res.add(B.get(j));

                 j++;

             }

             else if (i<A.size()) {

                 res.add(A.get(i));

                 i++;

             }

             else {

                 res.add(B.get(j));

                 j++;

             }

         }

         return res;

     }

 }