Merge Two Sorted Lists II

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

Note: You have to modify the array A to contain the merge of A and B. Do not output anything in your code.
TIP: C users, please malloc the result into a new array and return the result. 
If the number of elements initialized in A and B are m and n respectively, the resulting size of array A after your code is executed should be m + n

Example :

Input : 
         A : [1 5 8]
         B : [6 9]

Modified A : [1 5 6 8 9]
Method 1:

Sort

Solution:

Time: O(nlogn)
Space: O(1)

public class Solution {
    public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
        a.addAll(b);
        Collections.sort(a);
    }
}

Method 2:

Allocate a first, and then fill it from the end.

Solution:

Time: O(n)
Space: O(1)

public class Solution {
    public void merge(ArrayList<Integer> a, ArrayList<Integer> b) {
        int aSize = a.size();
        for (int i = 0; i < b.size(); i ++) {
            a.add(0);
        }
        int i = aSize - 1;
        int j = b.size() - 1;
        int p = a.size() - 1;
        while (i >= 0 && j >= 0) {
            int aVal = a.get(i);
            int bVal = b.get(j);
            if (aVal > bVal) {
                a.set(p, aVal);
                i --;
            } else {
                a.set(p, bVal);
                j --;
            }
            p --;
        }
        while (i >= 0) {
            a.set(p--, a.get(i--));
        }
        while (j >= 0) {
            a.set(p--, b.get(j --));
        }
    }
}